Graduate Center, CUNY
Fridays 11:30 am - 12:30 am
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.
PAST TALKS
Fall 2011 Talks
December 9, 2011: Kira Adaricheva, Yeshiva University, Room 8405
Title: On the bases of a finite closure system
In this talk we will present an overview of the concept of a basis for a finite closure system and consider various types of optimization problems connected to the bases such as finding the optimum, the minimum or the minimum unit bases. The problems of that sort appear in many abstract and applied areas such as relational data bases, logic programming, operations research and the theory of hypergraphs, to name a few. A classical result of the theory of closure systems is the existence of so-called canonical basis, independently discovered in 80s by D.Maier and by J.Guiques and V.Duquenne.
We use a lattice theoretic approach to introduce a new type of the basis, which is called a D-basis, and we show that it possesses the advantageous feature that is not shared by the canonical basis. Besides, in the closure systems with some additional properties, the D-basis can be further optimized to get the size less than the size of the canonical one.
The talk is based on two papers: one is written in collaboration with J.B.Nation (University of Hawaii) and R.Rand (undergrad student at Yeshiva University), the other is the paper in progress with J.B.Nation.
November 4, 2011: Lenny Tevlin, New York University
Title: Noncommutative Symmetric Functions with One and Two Parameters
Noncommutative symmetric functions have many properties analogous to those of classical (commutative) symmetric functions. For instance, ribbon Schur functions (analogs of the classical Schur basis) expand positively in noncommutative monomial and fundamental bases with combinatorially interesting expansion coefficients. The purpose of this talk is to introduce noncommutative symmetric functions which seem to be appropriate analogs of Hall-Littlewood and Macdonald polynomials.
October 28, 2011: Nathan Kahl, Seton Hall University
Title: Degree Sequences, Toughness, and Monotone Theorems
In this talk we look at theorems that take a graph's degree sequence and use that to determine whether the graph has a particular graphical property. The conditions in such theorems are almost always monotone: whenever a degree sequence satisfies the conditions, then any "larger" degree sequence necessarily satisfies them too. Somewhat surprisingly, very few best possible monotone theorems have been developed to date--even though there is a very simple way to check when a monotone theorem is best possible. We look at various properties where such best monotone theorems exist, some related properties for which there appear to be no best possible monotone theorems, and finally illustrate both cases by looking at the property of being t-tough for various values of t. In this case, for certain values of toughness we've managed to prove the best possible theorem, while for other values we've discovered and proved that these best possible theorems aren't actually possible.
October 21, 2011: Andrew King, Simon Fraser University
Title: Proving the Lovász-Plummer Conjecture
In the 1970s, Lovász and Plummer conjectured that every cubic bridgeless graph has exponentially many perfect matchings. This was proven by Voorhoeve for bipartite graphs and by Chudnovsky and Seymour for planar graphs. In this talk I will describe our proof of the general case, which uses elements of both aforementioned partial results as well as Edmonds' characterization of the perfect matching polytope. (Joint work with Louis Esperet, Frantiek Kardo, Daniel Král', and Sergey Norin.)
October 14, 2011: Irena Penev, Columbia University
Title: Scott's Conjecture for the Bull (and a Few Other Graphs)
Abstract
September 23, 2011: Kerry Ojakian, Saint Joseph's College, Room 8405
Title: Cops and Robber on the Hypercube, Part II
September 16, 2011: Kerry Ojakian, Saint Joseph's College, Room 8405
Title: Cops and Robber on the Hypercube, Part I
This is joint work with David Offner. The game of Cops and Robber is a two-player game played on an undirected graph. One player controls a number of cops, and the second player controls a single robber. To begin the game, the cops choose any vertices to occupy, and then the robber chooses a vertex to occupy. The players then take turns, at each turn remaining stationary or moving to an adjacent vertex. The cops win if they catch the robber, that is, if they ever occupy the same vertex as the robber; the robber wins if he can avoid being caught indefinitely. Given a particular graph, its "cop number" is the minimum number of cops needed for the cops to guarantee a win (for example, any path has cop number 1, any complete graph has cop number 1, and any cycle with at least 4 vertices has cop number 2). This game was first proposed by various authors in the 1970's and 1980's. Our work (in progress) has focused on analyzing this game when played on the hypercube. We have investigated what happens under various rules about who can move and who can remain still on a turn (in the standard game any agent can move or stay still on a given turn).
September 9, 2011: Christopher Hanusa, Queens College, CUNY, Room to be announced
This talk is actually part of the Workshop on Symmetric Groups
Time: 12:15 - 12:45
Title: Combinatorial interpretations in affine Coxeter groups of types B, C, and D
Abstract: Core partitions and abacus diagrams are two useful combinatorial objects in bijection with minimal length coset representatives in the parabolic quotient of the affine symmetric group modulo the finite symmetric group. In joint work with Brant Jones, we extend core partitions, abacus diagrams, and other combinatorial interpretations to types affine B, C, and D.
Spring 2011 Talks
April 15, 2011: Sam Hsiao, Bard College, Room 8405
Title: Enumerating chains in partially ordered sets
Abstract: The flag f-vector of a finite partially ordered set (poset) is a vector of positive integers whose entries enumerate chains (i.e., linearly ordered subsets) that pass through specified sets of ranks. What does the set of all flag f-vectors of fixed length look like as a subset Euclidean space? I will describe progress on this question that resulted from joint work with a colleague and two undergraduate students at Bard College. The main result is a simple characterization of the closed convex cone spanned by the flag f-vectors of fixed length. A key ingredient is to construct certain "limit posets" whose flag f-vectors are in some sense extremal, an idea that originated in the work of Billera and Hetyei.
Joint work with Lauren Rose, Shelley Stahl, and Ezra Winston.
April 8, 2011: Gyorgy Turan, University of Illinois at Chicago, Room 8405
Title: Horn formulas and directed hypergraphs
Abstract: Horn formulas (propositional formulas with clauses of the form
a,b --> c) are an expressive and tractable fragment of propositional
logic and have many applications. Horn formulas can also be
viewed as directed hypergraphs, generalizing directed graphs
which correspond to sets of clauses of the form a --> b.
We consider some of the combinatorial problems arising, such
as extremal problems and problems about random directed hypergraphs.
For example, the Horn formula motivation suggests questions about
reachability in directed hypergraphs, but the notion of
reachability (`forward chaining') differs from the usual notion
of reachability in a directed hypergraph.
Joint work with Marina Langlois, Dhruv Mubayi, Robert Sloan
and Despina Stasi.
April 1, 2011: Kira Adaricheva, Yeshiva University, Room 8405
Title: Finite Convex Geometries of Point Configurations
Abstract
March 25, 2011: Jonathan Cutler, Montclair State University, Room 8405
Title: Extremal problems related to graph homomorphisms
Abstract: There has recently been quite a bit of interest in problems related to minimizing or maximizing the number of homomorphisms among graphs in some class into a fixed (small) graph. For example, homomorphisms from a graph G to a path on two vertices, where one of the vertices is looped, correspond to independent sets in G. It is a consequence of the Kruskal-Katona theorem that the number of independent sets in a graph on a fixed number of vertices and edges is maximized by the lex graph (where edges form an initial segment under the lexicographic ordering). This talk will outline several results that are the product of joint work with A.J. Radcliffe, including the several involving independent sets in graphs and hypergraphs.
March 11, 2011: Julia Wolf, Ecole Polytechnique in Paris, Room 8404
This session is held jointly with the Number Theory Seminar
Title: Recent improvements on the cap set problem
Abstract: A cap set is a subset of F_3^n containing no 3-term arithmetic progressions. Until very recently, the best known upper bound on the density of a cap set was of the form c n^{-1} for some constant c. It is proved by a relatively simple Fourier-analytic argument due to Meshulam, which has stubbornly resisted improvement for many years. In this talk we shall try to explain some of the ingredients of recent ground-breaking work of Bateman and Katz, who obtained the bound c n^{-(1+epsilon)} for a small but positive epsilon.
March 4, 2011: Emilie Hogan, Rutgers University, Room 8405
Title: Somos Sequences - Past and Present
Abstract: In this talk I will introduce the famed Somos sequences: integer sequences produced by rational recurrences. After Michael Somos introduced these recurrences and sequences, the research area took off. Many people found related recurrences and developed techniques to prove integrality. I will first talk about the three types of proofs that were used to prove integrality of the original Somos sequences. Then I will talk about a recurrence, inspired by Somos, that I discovered with Paul Heideman at University of Wisconsin - Madison while working with Jim Propp. Finally, I will talk about recurrences that surprisingly generate rational numbers (when complex numbers are expected) that I have studied as part of my thesis.
Febuary 25, 2011: Debbie Yuster, SUNY Maritime College, Room 8405
Title: Finding Minimal Circuit Sets for Tropical Bases Using Matroids
Abstract: "Tropical" linear spaces are tropical geomtery's analog of ordinary linear spaces, in that they are intersections of tropical hyperplanes. A tropical basis for a tropical linear space is a generating set of sorts, however it need not be minimal. Some tropical linear spaces have associated matroids, and in the language of matroids, we will explore the now-combinatorial question of finding minimal tropical bases. No prior knowledge of tropical geometry necessary!
Febuary 18, 2011: Maria Chudnovsky, Columbia University, Room 8405 (Dining Commons Breakout Room)
Title: Tournament heroes
Abstract: The chromatic number of a tournament T is the smallest number of
transitive tournaments that partition V(T). Let us say that a tournament S
is a hero if for every tournament T not containing S, the chromatic number
of T is at most a constant c(S). Recently, in joint work with Eli Berger,
Krzysztof Choromanski, Jacob Fox, Martin Loebl, Alex Scott, Paul Seymour
and Stephan Thomasse, we proved a theorem that gives a complete
description of all heroes. This talk will describe the result, and survey
some of the proof ideas.
Previous Talks hosted by Janos Pach
