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 quasi-polynomial q-Queens 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 single-element 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 almost-graphic 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 3-connected proper minor of a 3-connected matroid M, then (with a few exceptions) we can construct M from N through a sequence of 3-connected matroids, each of which is a single-element 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 3-connected single-element extension or coextension, such that at most two consecutive single-element extensions occur in the sequence (unless the rank of the matroids involved are r(M)). Moreover, if two consecutive single-element 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 vice-versa
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 Calkin-Wilf tree
Abstract: The Calkin-Wilf 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 Calkin-Wilf 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 n-vertex graphs of minimum degree at least d, the graph that uniquely maximizes i(G) is K_{d,n-d}, 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.