check
Combinatorics: Noam Lifshitz (BIU) "The Junta Method in Extremal Hypergraph Theory and Chvátal’s conjecture" | Einstein Institute of Mathematics

Combinatorics: Noam Lifshitz (BIU) "The Junta Method in Extremal Hypergraph Theory and Chvátal’s conjecture"

Date: 
Sun, 25/06/201711:00-13:00
Location: 
Rothberg B221 (CS building)
Speaker: Noam Lifshitz (BIU)
Title:The Junta Method in Extremal Hypergraph Theory and Chvátal’s 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 by distinct new vertices.
We present a general approach to such problems, using a "junta approximation method" that originates in the 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, which effectively reduces the extremal problem to an easier problem on juntas. Using this approach we obtain (for all C We apply our method to Chvátal's conjecture (1974), 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 that n>n_0(d).
Joint work with Nathan Keller.