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

Abstract:

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>n₀(d).

Joint work with Nathan Keller.