Hypergraph properties

Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).

For \(r\ge3\) and \(n\ge r\), let \(E_{n,r}=\binom{[n]}r\); an element of \(\{0,1\}^{E_{n,r}}\) is an \(r\)-uniform hypergraph on \([n]\), and a hypergraph property is a function on this space invariant under the permutations of \([n]\). Friedgut and Kalai conjectured that increasing \(r\)-uniform hypergraph properties have threshold width \(O_{r,\varepsilon}((\log n)^{-r/(r-1)})\), and Bourgain and Kalai came within any power \((\log n)^\eta\) of it. This lesson proves the conjecture [OpenAI-T2]:

Theorem 3.1 (OpenAI). For every \(r\ge3\) there is a constant \(C_r\) such that for every \(n\ge r\), every \(0<p<1\) and every hypergraph property \(f:\{0,1\}^{E_{n,r}}\to\{0,1\}\), \[ \operatorname{Var}_p(f)\le\frac{C_r}{(\log n)^{r/(r-1)}}\,I_p(f). \]

Corollary 3.2 (OpenAI). For a nontrivial increasing property of \(r\)-uniform hypergraphs on \(n\ge r\) vertices and \(0<\varepsilon<\frac12\), \(p_{1-\varepsilon}-p_\varepsilon\le\frac{2C_r}{(\log n)^{r/(r-1)}}\log\frac{1-\varepsilon}\varepsilon\).

The proof follows Vertex blocks and graph properties: restrict to the edges meeting a random block \(B\) of about \(\sqrt n\) vertices, bound the restricted low-degree mass by the hypercontractive estimate, and transfer it to the original Fourier degrees. The one change is combinatorial: an \(r\)-uniform hypergraph with \(s\) edges has a vertex of degree between \(1\) and \(rs^{(r-1)/r}\), so restricted degrees up to \(k\) control original degrees up to \((k/r)^{r/(r-1)}\). With \(k\) of order \(\sigma\log n\), the exponent becomes \(r/(r-1)\), and the factor \(\sigma^{2-r/(r-1)}\), with a positive exponent, makes the bound uniform in the bias.

We use Lemmas 2.1, 2.2 and 4.1 of Biased Fourier analysis and hypercontractivity and Lemma 1.1 of Vertex blocks and graph properties, whose statement and proof hold verbatim for any finite coordinate set and any subset \(F\) of it. Throughout \(\alpha=\frac r{r-1}\in(1,2)\), \(\sigma=\sqrt{p(1-p)}\), and \(F_B=\{e\in E_{n,r}:e\cap B\neq\varnothing\}\).

1. The block estimate

Lemma 1.1. Let \(r+1\le m\le n\), \(B\) uniform among the \(m\)-subsets of \([n]\), and \(k=\frac{\sigma\log m}{64}\). For every hypergraph property \(f\), \[ \begin{aligned} &\sum_{S\subseteq E_{n,r}}\mathbb P_B\bigl(1\le|S\cap F_B|\le k\bigr)\,\widehat f(S)^2\\ &\quad \le m^{-1/4}\,\frac{rm}n\,I_p(f). \end{aligned} \]

Proof. Fix \(B\) and an assignment \(y\) of the edges disjoint from \(B\). The permutations supported on \(B\) fix every such edge, so \(f_y\) is invariant under them. An edge with \(j\ge1\) vertices in \(B\) has an orbit of size \(\binom mj\ge m\), since \(1\le j\le r<m\): its part outside \(B\) is fixed and its part inside can be any \(j\)-subset of \(B\). So \(I_e(f_y)\le I(f_y)/m\) on \(F_B\), and Lemma 4.1 of Biased Fourier analysis and hypercontractivity applies to \(f_y\). Average over \(y\) with Lemma 1.1 of Vertex blocks and graph properties, and then over \(B\), using \(\mathbb P(e\in F_B)\le rm/n\) by a union bound over the \(r\) vertices of \(e\). \(\square\)

2. Capturing a support

Lemma 2.1. Let \(1\le m\le n\), \(k>0\), \(L=(k/r)^\alpha\), and suppose \(rL\frac{m-1}{n-1}\le\frac12\). For a uniform \(m\)-subset \(B\) and every \(S\subseteq E_{n,r}\) with \(1\le|S|\le L\), \[ \mathbb P_B\bigl(1\le|S\cap F_B|\le k\bigr)\ge\frac m{2n}. \]

Proof. Let \(s=|S|\), \(V=\bigcup_{e\in S}e\) and \(v=|V|\). Since \(s\le\binom vr\le v^r\), the average degree is \(\frac{rs}v\le rs^{(r-1)/r}\le rL^{(r-1)/r}=k\); choose \(u\in V\) with \(1\le d_S(u)\le k\). As in Lemma 3.1 of Vertex blocks and graph properties, \(\mathbb P(B\cap V=\{u\})\ge\frac mn\bigl(1-(v-1)\frac{m-1}{n-1}\bigr)\), which is at least \(\frac m{2n}\), using \(v\le rs\le rL\). On this event the edges of \(S\) meeting \(B\) are those containing \(u\), so \(|S\cap F_B|=d_S(u)\in[1,k]\). \(\square\)

Combining the two lemmas, whenever both apply, \[ \begin{aligned} &\sum_{1\le|S|\le L}\widehat f(S)^2\\ &\quad \le2r\,m^{-1/4}I_p(f). \end{aligned}\tag{2.1} \]

3. The theorem

Proof of Theorem 3.1. Choose an integer \(N_r>r\) such that for all \(n\ge N_r\) and \(m=\lfloor\sqrt n\rfloor\): \[ \begin{gathered} m\ge r+1,\qquad \log m\ge\tfrac13\log n,\\ r(\log n)^\alpha n^{-1/2}\le\tfrac12,\\ m^{-1/4}(\log n)^\alpha\le1; \end{gathered} \] this is possible because every power of \(\log n\) grows more slowly than every positive power of \(n\). Let \(n\ge N_r\), \(k=\frac{\sigma\log m}{64}\) and \(L=(k/r)^\alpha\). Since \(k/r\le\log n\) and \(\frac{m-1}{n-1}\le n^{-1/2}\), Lemma 2.1 applies, and (2.1) gives \[ \sum_{1\le|S|\le L}\widehat f(S)^2\le\frac{2r}{(\log n)^\alpha}I_p(f). \] By Lemma 2.1 of Biased Fourier analysis and hypercontractivity, \[ \begin{aligned} &\sum_{|S|>L}\widehat f(S)^2\le\frac1L\sum_S|S|\widehat f(S)^2\\ &\quad =\frac{\sigma^2}LI_p(f),\\ &\frac{\sigma^2}L=\frac{(64r)^\alpha\sigma^{2-\alpha}}{(\log m)^\alpha}\\ &\quad \le\frac{(192r)^\alpha}{(\log n)^\alpha}, \end{aligned} \] because \(2-\alpha=\frac{r-2}{r-1}>0\) and \(\sigma\le1\). Adding, \(\operatorname{Var}_p(f)\le\frac{2r+(192r)^\alpha}{(\log n)^\alpha}I_p(f)\). For \(r\le n<N_r\), \(\operatorname{Var}_p(f)\le\sigma^2I_p(f)\), which is at most \(\frac14I_p(f)\le\frac{(\log N_r)^\alpha}{4(\log n)^\alpha}I_p(f)\). So \(C_r=\max\{2r+(192r)^\alpha,\frac14(\log N_r)^\alpha\}\) works. \(\square\)

Proof of Corollary 3.2. Let \(q(p)=\mathbb E_pf\). By the Margulis–Russo formula (Lemma 2.2 of Biased Fourier analysis and hypercontractivity), \(q'(p)=I_p(f)\). The complete hypergraph has the property and the empty one does not, so \(0<q(p)<1\) for \(0<p<1\). By Theorem 3.1, \(\frac{d}{dp}\log\frac q{1-q}=\frac{q'}{q(1-q)}\ge\frac{(\log n)^\alpha}{C_r}\), so \(q\) is strictly increasing, the quantiles are unique, and integrating from \(p_\varepsilon\) to \(p_{1-\varepsilon}\) gives \(2\log\frac{1-\varepsilon}\varepsilon\ge\frac{(\log n)^\alpha}{C_r}(p_{1-\varepsilon}-p_\varepsilon)\). \(\square\)

For \(r=2\) the same argument gives exponent \(2\), as in Vertex blocks and graph properties, where the sharper count \(s<v^2/2\) improves the constants. The bound in Theorem 3.1 holds for every hypergraph property, monotone or not, and at every bias \(p\).

4. Exercises

Exercise 4.1 (easy). Show that the orbit of an edge with \(j\) vertices in \(B\), under the permutations supported on \(B\), has \(\binom mj\) elements, and that \(\binom mj\ge m\) for \(1\le j\le r<m\).

Exercise 4.2 (easy). Show that an \(r\)-uniform hypergraph with \(s\ge1\) edges has a vertex of degree between \(1\) and \(rs^{(r-1)/r}\).

Exercise 4.3 (medium). Show that \(\frac{\sigma^2}L\le\frac{(64r)^\alpha}{(\log m)^\alpha}\) for every \(0<p<1\), and explain why the argument would fail as \(p\to0\) if the exponent \(\alpha\) were larger than \(2\).

Exercise 4.4 (easy). Show that the denominators \((\log n)^\alpha\) and \((\log\binom nr)^\alpha\) are comparable for fixed \(r\): \(\frac12\log n\le\log\binom nr\le r\log n\) for \(n>r\).

5. Solutions

4.1. A permutation supported on \(B\) maps \(e=e_{\rm in}\cup e_{\rm out}\), \(e_{\rm in}\subseteq B\), to \(\pi(e_{\rm in})\cup e_{\rm out}\), and these permutations act transitively on the \(j\)-subsets of \(B\). For \(1\le j\le m-1\), \(\binom mj\ge\binom m1=m\).

4.2. With \(v\) vertices of positive degree, \(s\le\binom vr\le v^r\), so \(v\ge s^{1/r}\), and the average degree \(rs/v\le rs^{1-1/r}\); some vertex has degree at most the average and at least \(1\).

4.3. \(\frac{\sigma^2}L=\frac{\sigma^2(64r)^\alpha}{(\sigma\log m)^\alpha}=\frac{(64r)^\alpha\sigma^{2-\alpha}}{(\log m)^\alpha}\), and \(\sigma^{2-\alpha}\le1\) because \(\sigma\le1\) and \(2-\alpha>0\). For \(\alpha>2\) the factor \(\sigma^{2-\alpha}\) would be unbounded as \(p\to0\); for graphs (\(\alpha=2\)) the powers of \(\sigma\) cancel exactly.

4.4. \(\binom nr\le n^r\) gives the upper bound. For \(1\le r\le n-1\), \(\binom nr\ge n\), and \(n>\sqrt n\); so \(\log\binom nr\ge\frac12\log n\) (indeed for all \(n>r\)).

References