Combinatorics Seminar

When: Sunday, November 12, 10am
Where: Schreiber 309
Speaker: Noam Lifshitz, Bar-Ilan University
Title: The junta method in extremal combinatorics and Chvátal's simplex conjecture


Numerous problems in extremal hypergraph theory ask to determine the maximal size of a k-uniform hypergraph  on n vertices that does not contain an "enlarged" copy H+ of a fixed hypergraph H, obtained from H by  enlarging each of its edges with distinct new vertices. 

We present a general approach to such problems, using a "junta approximation method" that originates from analysis of Boolean functions. We show that any H+-free hypergraph is essentially contained in a "junta" - a hypergraph determined by a small number of vertices - that is also H+-free. Using this approach, we obtain (for all C<k<n/C) a characterization of all hypergraphs H for which the maximal size of an H+-free family is {{n-t}\choose{k-t}}, in terms of intrinsic properties of H.

We apply our method to the 1974 Chvátal's conjecture, which asserts that for any d<k<\frac{d-1}{d}n, the maximal size of a k-uniform family that does not contain a d-simplex (i.e., d+1 sets with empty intersection such that any d of them intersect) is {{n-d-1}\choose{k-d-1}}. We prove the conjecture for all d and k, provided n>n0(d).

Joint work with Nathan Keller.