The Junta Method for Hypergraphs and the Erdős-Chvátal 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$. These include well-known problems such as the Erdős-Sós `forbidding one intersection' problem and the Frankl-Fü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 Erdős-Chvátal simplex conjecture, which asserts that for any $d<k\le \frac{d}{d+1}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 $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$. We prove the conjecture for all $d$ and $k$, provided $n>n_0(d)$.

Revised version, to appear in Advances in Mathematics. Significant exposition changes. 81 pages, no figures

Cited by in corpus (1)

• Simple juntas for shifted families