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 excludedminor 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 kcopwin
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 Updown 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 updown 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 updown signatures of microarray curves defined by Willbrand et al by using Foulkes’ method for enumeration of permutations with prescribed updown 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 RobinsonSchenstedKnuth 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 onetoone 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 $s1$, 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 quasipolynomial 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: qLassalle 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 qgeneralization related to the standard qCatalan numbers, resulting in palindromic polynomials with positive integer coefficients. Conjecturally, similar qsequences related to Carlitz's qCatalan numbers, Gessel's generalized qCatalan, qBallot, and qsuper 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 Dbasis, 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 Drelation 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
Spring 2013
Fall 2012
Spring 2012
Fall 2011
Spring 2011
Previous Talks hosted by Janos Pach
