Discrete Geometry and Combinatorics Seminar

Ernest ChongCornell University
Kruskal-Katona-type theorems

Monday, January 26, 2015 - 2:30pm
Malott 206

The Kruskal-Katona theorem, proven around the 1960s, is a classic result in combinatorics that characterizes the $f$-vectors of simplicial complexes. In 1977, Stanley noticed that Macaulay's well-known characterization of the Hilbert functions of graded ideals of polynomial rings is equivalent to a multiset analogue of the Kruskal-Katona theorem. Later in 1988, Frankl-Füredi-Kalai found a graph-theoretic analogue of the Kruskal-Katona theorem. The purpose of this talk is to reconcile these Kruskal-Katona analogues using the algebraic notion of Macaulay-Lex rings. We will show that these analogues are in fact special cases of one main theorem.