The junta method in extremal hypergraph theory and Chvátal's conjecture

DOI10.1016/J.ENDM.2017.07.027zbMATH Open1379.05083arXiv1707.02643OpenAlexW2744160631WikidataQ123219023 ScholiaQ123219023MaRDI QIDQ1689997FDOQ1689997

Authors: Nathan Keller, Noam Lifshitz

Publication date: 18 January 2018

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

. These include well-known problems such as the ErdH{o}s-S'{o}s `forbidding one intersection' problem and the Frankl-F"{u}redi `special simplex' problem. 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 < k < n / C

, a complete solution of the extremal problem for a large class of

H

's, which includes the aforementioned problems, and solves them for a large new set of parameters. We apply our method also to the 1974 ErdH{o}s-Chv'{a}tal simplex conjecture, which asserts that for any