Graduate Center, CUNY

Fridays 11:30 am - 12:30 am in 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.

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, František 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.