## 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_{0}(d).
Joint work with Nathan Keller.