New York Combinatorics Seminar
Graduate Center, CUNY
Fridays 11:30 am  12:30 am Room 8405
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, Christopher Hanusa, Sandra Kingan, and Kerry Ojakian.
Spring 2012 Talks
February 3, 2012: Christopher R. H. Hanusa (Queens College, CUNY)
Title: A quasipolynomial qQueens result and related Kronecker products of matrices
Abstract: For a fixed number of nonattacking queens placed on a square board of varying size, we show that the number of solutions is a quasipolynomial function of the size of the board using Ehrhart theory. This result generalizes to other real and fairy pieces on a polygonal board. Determining the period of each quasipolynomial function requires calculating the least common multiple of all subdeterminants of a matrix. This matrix has the form of a Kronecker product of a matrix involving the moves of the piece and the incidence matrix of a complete graph. Investigation of this quantity gives a new linear algebraic result proved using graph theory. No background knowledge is necessary to enjoy this talk.
February 10, 2012: Sandra Kingan (Brooklyn College, CUNY)
Title: Excluded Minor Results  Survey
Abstract: Excluded minor theorems are some of the most celebrated results in graph and matroid structure theory. For a given class of matroids with a specified structure, a minimal excluded minor is a matroid that is not in the class, but every singleelement deletion and contraction is in the class. Such matroids are minimal obstructions for membership in the class. For example, the complete graph on five vertices and the complete bipartite graph with three vertices in each class are the minimal obstructions to planarity in graphs. Several classes of matroids such as binary, ternary, and quaternary matroids can be characterized in terms of their minimal obstructions. The opposite approach to excluded minor problems is to select a certain set of matroids for exclusion and describe the structure of the resulting class. This approach gives rise to decomposition results of the type initiated by Paul Seymour in his 1980 paper on the decomposition of regular matroids. I will give an overview of excluded minor results and describe some of my work in this area. I will also describe how Manoel Lemos and I solved the problem of characterizing the almostgraphic matroids by giving decomposition results for several classes of binary matroids.
February 17, 2012: Sandra Kingan (Brooklyn College, CUNY)
Title: Excluded Minor Results  Techniques
Abstract: This is joint work with Manoel Lemos. We present a strengthening of the Splitter Theorem and some of its applications to excluded minor results. The Splitter Theorem states that, if N is a 3connected proper minor of a 3connected matroid M, then (with a few exceptions) we can construct M from N through a sequence of 3connected matroids, each of which is a singleelement extension or coextension of the previous one. Note that that there is no condition on how many extensions may occur before a coextension must occur. We strengthen it, as a result of which we can obtain, up to isomorphism, M starting with N and at each step doing a 3connected singleelement extension or coextension, such that at most two consecutive singleelement extensions occur in the sequence (unless the rank of the matroids involved are r(M)). Moreover, if two consecutive singleelement extensions by elements {e, f} are followed by a coextension by element g, then {e, f, g} form a triad in the resulting matroid. Using the Strong Splitter Theorem and a matrix approach to extensions and coextensions, we can give a decomposition theorem for binary matroids with no prism minor.
February 24, 2012: No talk
March 2, 2012: Jonathan Cutler (Montclair State University)
Title: The interlace polynomial of forests
Abstract: The interlace polynomial is a graph polynomial introduced by Arratia, Bollobas, and Sorkin in order to address a problem related to DNA sequencing by hybridization. While explicit formulas for various classes of graphs have been found, including paths, it is natural to ask whether or not the interlace polynomial is a generating function for some structure in the graph. In this talk, we introduce a type of independent set, which we call an earlier sibling cover, and show that the interlace polynomial is a generating function for earlier sibling covers in forests. This is joint work with Colin Anderson, Jamie Radcliffe, and Lorenzo Traldi.
March 9, 2012: No talk
March 16, 2012: No talk
March 23, 2012: Stefan van Zwam (Princeton University)
Title: Beyond Total Unimodularity
Abstract: A matrix is totally unimodular if the determinant of each square submatrix
is in {1, 0, 1}. Such matrices are a cornerstone of the theory of integer
programming. The deepest result on such matrices is Seymour's decomposition
theorem. The only known way to test efficiently whether a matrix is totally
unimodular makes use of this theorem. Recently, Whittle introduced several classes of matrices with similar
properties: the determinants of the submatrices are restricted to a certain
set. In this talk I will discuss some results from the theory of totally
unimodular matrices from the point of view of matroid theory, and outline
which of those results will, won't, or might generalize to Whittle's classes.
In particular I will sketch an extension of Kirchhoff's matrix tree theorem
to quaternionic unimodular matrices. That result is joint work with
Rudi Pendavingh.
March 30, 2012: Amanda Redlich, Rutgers University
Title: Connecting disconnected graphs and viceversa
Abstract: Given a graph G with connected components G_1, ... G_k, when is it
possible to construct a connected graph H that is uniquely decomposable
into G_1, ... G_k? In this talk, we answer this question for all graphs
with small values of k and infinite families of graphs for arbitrary k.
This question originally arose in an extension of Kolaitis and
Kopparty's paper on parity and random graphs; we also discuss this
application of the uniquely decomposable construction.
April 6, 2012: Spring Break
April 13, 2012: Spring Break
April 20, 2012: Melvyn Nathanson, Lehman College, CUNY
Title: On the CalkinWilf tree
Abstract: The CalkinWilf tree is a binary tree whose vertices are the positive rational numbers. Every rational number occurs in the tree exactly once and in the form a/b, where are a and b are relatively prime positive integers. The purpose of this note is to construct analogous trees for linear fractional transformations and for the Gaussian numbers, and to prove that they inherit the essential properties of the rational number CalkinWilf tree.
April 27, 2012: James Alexander, Montclair State University
Title: Independent sets in graphs with given minimum degree
Abstract: The enumeration of independent sets in graphs with various degree restrictions has been a topic of much interest lately. Let i(G) be the number of independent sets in a graph G. Given a positive integer d, the question of which graph of minimum degree at least d maximizes i(G) is still unanswered. Galvin conjectured that given positive integers n and d, among all nvertex graphs of minimum degree at least d, the graph that uniquely maximizes i(G) is K_{d,nd}, provided that it satisfies the minimum degree condition (equivalently, provided that n>= 2d). Galvin proved an asymptotic version of this conjecture in 2011. We explain that an even stronger result may hold, and prove it for all bipartite graphs, and for the case when n=2d. We also show how Galvin's original conjecture is a corollary in these cases, and provide strong evidence for the stronger conjecture (and thus Galvin's as well) in the general case.
May 4, 2012: Thomas Zaslavsky, Binghamton University, SUNY
Title:Switching Automorphisms of Signed Graphs
Abstract: A signed graph is a graph with edges signed positive or negative. The
essential property of a signed graph is the list of circles whose sign
product is positive. A graph automorphism that preserves that list is
called a 'switching automorphism'. I will discuss the theory and
practice of switching automorphisms with emphasis on the Petersen and
Heawood graphs.
March 11, 2012: No talk
May 18, 2012: Karell Bertet, Laboratory L3i, La Rochelle University, France
Title: Lattices and rule bases: a state of the art of structural, algorithmics and applications aspects
Abstract: The first reference book on lattice theory is due to Birkhoff in 1940 (first edition). However, the structure of lattice has been introduced in the late 19th century as an algebraic structure equipped with two operators called lower and upper bound. Since the 2000s, the emergence of formal concept analysis (FCA) in various areas of computing, as in data mining and knowledge representation for databases and ontologies, has highlighted the structures of concept lattice and closed set lattice. The emergence of the lattice structure can be explained both by the growing share of computer science in most disciplines, leading to increasing production data, but also by the increasing power of computers. Indeed, although the size of the lattice can be exponential according to the data in the worst case, the development of many applications using lattices is now possible. However, the size of the lattice remains reasonably practicable, and the need for efficient algorithms to manipulate these structures is a major challenge.
In an application framework, efficient operation of the existing algorithms to manipulate these structures requires a good knowledge of the formalism and structural properties of the lattice theory to identify algorithmic tools suitable for a given problem. This seminar aims to present the basic concepts of lattice theory, and key generation algorithms of objects composing it, in particular rules basis and closure system. Some examples of use in classification and knowledge representation will also be presented.
