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 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.