Colloquium: Nathan Keller (Bar Ilan) - The junta method for hypergraphs and the Erdos-Chvatal simplex conjecture

Thu, 08/11/201814:30-15:30
Manchester Building (Hall 2), Hebrew University Jerusalem
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. These include well-known problems such as the Erdos-Sos 'forbidding one intersection' problem and the Frankl-Furedi 'special simplex' problem.
In this talk we present a general approach to such problems, using a 'junta approximation method' that originates from analysis of Boolean functions. We prove 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 also to the 1974 Erdos-Chvatal simplex conjecture, which asserts that for any dn_0(d).
Joint work with Noam Lifshitz.