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 2011 Talks
April 15, 2011: Sam Hsiao, Bard College, Room 8405
Title: Enumerating chains in partially ordered sets
Abstract: The flag fvector 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 fvectors 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 fvectors of fixed length. A key ingredient is to construct certain "limit posets" whose flag fvectors 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 KruskalKatona 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 3term 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 Fourieranalytic 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 groundbreaking 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 nowcombinatorial 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
