New York Combinatorics Seminar Graduate Center, CUNY Fridays 11:30 am - 12:30 am Room 4422 This seminar covers a wide range of topics in combinatorics and its applications to other disciplines, especially computer science. The CUNY Graduate Center is located at 365 Fifth Avenue (at the corner of 34th Street), New York. It can be easily approached by subway, using the B,D,F,N,Q,R, or 6 trains. Seminar organizers are Jonathan Cutler, Ezra Halleck, Christopher Hanusa, Sandra Kingan, and Kerry Ojakian. Fall 2013 Talks September 20, 2013: Dillon Mayhew (Victoria University of Wellington, New Zealand) Title: Characterizing representable matroids Abstract: Matroids abstract the notions of linear/geometric/algebraic dependence. More specifically, a matroid consists of a finitecollection of points, and a distinguished family of dependent subsets. If we take a finite collection of vectors from a vector space, and distinguish the linearly dependent subsets, then the result is a matroid, and we say that such a matroid is representable. The original motivating problem in matroid theory involves deciding which matroids are representable and which are not. A large fraction of the research in the area has been driven by this problem. This talk will be an introduction to matroid theory, and a survey of recent developments in the characterization of representable matroids. The focus will be on excluded-minor characterizations and formal languages. No knowledge of matroids will be assumed. October 4, 2013: Anthony Weaver (Bronx community College, CUNY) Title: Dessins and Curves Abstract October 18, 2013: Nancy Clarke (Acadia University, Nova Scotia, Canada) Title: Cops and Robber: Strategies and Characterizations Abstract: In this talk, we survey the pursuit and evasion game Cops and Robber. We focus on several characterizations of the graphs on which k cops have a winning strategy which generalize the corresponding characterizations in the one cop case. In particular, we give a relational characterization of k-copwin graphs, for all finite k, and a vertex elimination order characterization of such graphs. Our results hold for variations of the game and some extend to infinite graphs. November 8, 2013: Sanju Vaidya (Mercy College) Title: Young Tableaux and Up-down sequences of permutations for gene expressions Abstract: Young tableaux are certain tabular arrangements of integers. Alfred Young introduced them to describe irreducible representations of the symmetric group at the end of the 19th century. We will use combinatorial algorithms of permutations and Young tableaux to describe modifications of the research methods of Willbrand et al and Ahnert et al for identifying significant genes in the biological processes studied in microarray experiments. In the last decade, DNA microarrays (DNA chips) have been used to study gene expressions in many diseases such as cancer and diabetes. Willbrand et al introduced a new method of identifying significant genes by analyzing probabilities of up-down signatures of microarray expression curves of genes. Ahnert et al generalized the method of Willbrand et al and established various bounds on any microarray curve’s algorithmic compressibility which measures its significance in underlying biological process. We will compute the probabilities of up-down signatures of microarray curves defined by Willbrand et al by using Foulkes’ method for enumeration of permutations with prescribed up-down sequences and the hook length formula of Frame et al. Moreover, we will compute the bound of Ahnert et al corresponding to the map which gives the number of permutations with the same pattern of rises and falls for any microarray curve’s algorithmic compressibility. Using the Robinson-Schensted-Knuth procedure, we will associate Young tableaux to permutations corresponding to the data points of microarray curves. We will calculate the bound of Ahnert et al corresponding to the map which gives the length of the longest increasing or decreasing subsequence of a permutation. It is fascinating to see that how combinatorial algorithms of permutations and Young tableaux are useful in analyzing data of gene expressions and identifying significant genes in biological processes. November 15, 2013: Mohammad Nikouei (Stevens Institute of Technology) Title: Length Function for Weyl Groups of Extended Affine Root Systems of Type $A_1$ Abstract November 22, 2013: Melvyn Nathanson (Lehman College) Title: Cantor polynomials for semigroup sectors Abstract: A packing function on a set $\Omega$ in $\R^n$ is a one-to-one correspondence between the set of lattice points in $\Omega$ and the set $\N_0$ of nonnegative integers. It is proved that if $r$ and $s$ are relatively prime positive integers such that $r$ divides $s-1$, then there exist two distinct quadratic packing polynomials on the sector $\{ (x,y) \in \R^2 : 0 \leq y \leq rx/s\}$. For the rational numbers $1/s$, these are the unique quadratic packing polynomials. Moreover, quadratic quasi-polynomial packing functions are constructed for all rational sectors. December 6, 2013: Ebad Mahmoodian (Sharif University of Technology, Tehran, Iran) Title: Defining sets in combinatorics with emphasis in graph theory Abstract December 13, 2013: Lenny Tevlin (New York University) Title: q-Lassalle Polynomials and their Generalizations Abstract: In 2010 Michel Lassalle (http://arxiv.org/abs/1009.4225) proved a conjecture of Zeilberger about two sequences of integers related to Catalan numbers. These sequences have a natural q-generalization related to the standard q-Catalan numbers, resulting in palindromic polynomials with positive integer coefficients. Conjecturally, similar q-sequences related to Carlitz's q-Catalan numbers, Gessel's generalized q-Catalan, q-Ballot, and q-super Ballot numbers also lead to polynomials with positive integer coefficients. December 20, 2013: Kira Adaricheva (Yeshiva University, NY and Nazarbayev University, Kazakhstan) Title: Discovery of the strong association rules in binary tables using the hypergraph dualization Abstract: Discovery of (strong) association rules, or implications, is an important task in data management, and it finds application in artificial intelligence, data mining and semantic web. We introduce the novel approach for the discovery of a specific set of implications, called the D-basis, which provides a representation for a reduced binary table, based on the structure of its Galois lattice. At the core of the method is the D-relation defined in the lattice theory framework, and the hypergraph dualization algorithm that allows to effectively produce the set of transversals for a given Sperner hypergraph. The latter algorithm developed by specialists from Rutgers Center for Operations Research and further improved by specialists from National Institute of Informatics in Japan, has already found numerous applications in solving the optimization problems in data base theory, artificial intelligence and game theory. This is joint work with J.B.Nation (University of Hawaii). Previous Speakers