1 Introduction
Let r\ge3 and n\ge r be integers, write [n]=\{1,\ldots,n\}, and put E_{n,r}=\binom{[n]}r. An element of \{0,1\}^{E_{n,r}} represents a simple r-uniform hypergraph. A hypergraph property is a Boolean function on this space that is invariant under every permutation of [n]. For 0<p<1, give the coordinates the independent Bernoulli(p) law, and denote expectation and variance by \E_p and \Var_p.
For an edge e, let x_{e\leftarrow b} be x with its e-coordinate set to b. Define the pivotal influence of e and the total influence of f by
The probability in the first expression is over the other coordinates; it does not include an additional factor of p(1-p). All logarithms are natural, and n always counts vertices.
Theorem 1.1. For every integer r\ge3 there is a finite constant C_r such that, for every integer n\ge r, every 0<p<1, and every hypergraph property f:\{0,1\}^{E_{n,r}}\to\{0,1\},
No monotonicity assumption is required.
The theorem measures how vertex symmetry forces sensitivity to edge changes. If the probability of a property stays bounded away from zero and one, its total influence must grow at least as (\log n)^{r/(r-1)}.
A property is increasing if changing coordinates from 0 to 1 cannot decrease its value, and nontrivial if it is not constant. For a nontrivial increasing property, put q(p)=\E_p f and define p_a=\inf\{p\in[0,1]:q(p)\ge a\} for 0<a<1. For fixed 0<\varepsilon<1/2, its threshold width is p_{1-\varepsilon}-p_\varepsilon. Friedgut and Kalai conjectured that this width is at most O_{r,\varepsilon}((\log n)^{-r/(r-1)}) for every increasing r-uniform hypergraph property [5, Section 5, p. 2999]. Their formulation counts edge coordinates rather than vertices; for fixed r, \log\binom nr\sim r\log n as n\to\infty. Corollary 4.1 proves this conjectured bound by integrating (1.1), with an explicit dependence on \varepsilon.
Context and attribution. Kahn, Kalai, and Linial [6] established a fundamental link between Fourier analysis and the influences of Boolean functions. For a function invariant under a transitive group on M coordinates, their theorem gives a total-influence lower bound of order \Var_{1/2}(f)\log M at the uniform measure. Bourgain, Kahn, Kalai, Katznelson, and Linial [3] extended the influence method to product spaces. Friedgut and Kalai [5] used influence inequalities to prove sharp thresholds for increasing families with transitive symmetry. For hypergraph properties, the induced action on the \binom nr edge coordinates is transitive. The richer structure of vertex permutations, however, contains more information than this single transitivity statement.
Bourgain and Kalai [4, Corollary 4.1] studied how group actions on sets of coordinates improve influence estimates. For fixed r and every \eta>0, their result gives a lower bound of order \Var_{1/2}(f)(\log n)^{r/(r-1)-\eta} for the total influence of a hypergraph property at the uniform measure. Their influence results already allow nonmonotone functions. Kelman, Kindler, Lifshitz, Minzer, and Safra obtained further estimates for group-invariant functions [7]. For graph properties, these give I_{1/2}(f)\ge c\Var_{1/2}(f)(\log n)^2/(\log\log n)^2 for sufficiently large n; see the arXiv version cited in [7, Section 7.4]. The present proof uses vertex symmetry through restrictions: all edges touching a vertex block remain free, and only edges wholly outside the block are fixed. This is the method of the companion manuscript A Sharp Threshold Bound for Monotone Graph Properties [9, Theorem 1.2 and Sections 2–3], which establishes the corresponding variance bound with denominator (\log n)^2 for graph properties, uniformly in p and without monotonicity. We reproduce its Fourier estimate and restriction argument in full. The additional combinatorial step replaces the graph degree estimate by its r-uniform counterpart, producing the exponent r/(r-1).
Proof strategy. Put \sigma=\sqrt{p(1-p)} and \alpha=r/(r-1). The Fourier expansion for the Bernoulli product measure is indexed by sets S of hyperedges. Its squared nonconstant coefficients sum to the variance; weighting them by |S| gives \sigma^2I_p(f). Thus the influence controls high degrees. The task is to bound the remaining mass using symmetry.
For large n, choose a uniformly random block B of m vertices, with m about \sqrt n, and leave free all edges meeting B. Every permutation within B survives an assignment to the other coordinates, and every free-edge orbit has at least m elements. Section 2 bounds the restricted Fourier mass up to a degree k proportional to \sigma\log m by m^{-1/4} times the restricted total influence. Its linear dependence on influence allows averaging over the assigned coordinates.
Regard a nonempty Fourier index S as an r-uniform hypergraph with s edges. It has a vertex of positive degree at most r s^{(r-1)/r}. For s\le L=(k/r)^\alpha, this degree is at most k. The event that B meets the union of these edges only at that vertex has probability comparable to m/n and leaves between one and k support edges free. After averaging over the assignments and B, the restricted total influence is at most (rm/n)I_p(f), so the two factors of m/n cancel. Section 3 thereby controls the original Fourier mass up to degree L.
Since L is of order (\sigma\log n)^\alpha, the remaining mass is at most \sigma^2I_p(f)/L, with coefficient of order \sigma^{2-\alpha}(\log n)^{-\alpha}. The positive exponent 2-\alpha makes this bound uniform in p. Section 4 completes the estimate and derives the threshold consequence.
2 A Fourier estimate for small individual influences
We first work on an arbitrary finite coordinate set J. Our objective is to control low-degree Fourier mass when every individual influence is small relative to the total. We follow the elementary argument in [9, Lemma 2.1]; its analytic ingredient is a two-to-four norm estimate of the type underlying the classical hypercontractive inequalities [2, 1]. The proof below includes the dependence on the bias.
Fix 0<p<1 and put \sigma=\sqrt{p(1-p)}. For i\in J and A\subseteq J, define
Independence, zero means, and unit second moments show that the \chi_A form an orthonormal basis. Write \widehat h(A)=\E_p[h\chi_A]. Throughout this section, norms and expectations use this product law, and I_i(h) and I(h) denote pivotal and total influence on J.
For Boolean h, let \Delta_i h be the function on the other coordinates obtained by subtracting the section at x_i=0 from the section at x_i=1. Direct expectation in coordinate i gives
Because \Delta_i h\in\{-1,0,1\}, Parseval’s identity yields
In particular, this identity uses no sign condition on \Delta_i h.
Lemma 2.1 (Low-degree mass). Let m\ge2 be real and let h:\{0,1\}^J\to\{0,1\} satisfy I_i(h)\le I(h)/m for every i\in J. With k=\sigma\log m/64, one has
The sum is empty when k<1.
Proof. We will use a two-to-four norm estimate to bound low-degree projections of the differences \Delta_i h. Set \rho=\sigma/4 and define the linear operator T by T\chi_A=\rho^{|A|}\chi_A. We first prove
for every real-valued function g on the product space. For one coordinate, |\chi_i|\le1/\sigma and \E\chi_i^2=1 imply |\E\chi_i^3|\le1/\sigma and \E\chi_i^4\le1/\sigma^2. For real a,b, expansion and 2|ab^3|\le a^2b^2+b^4 give
where the last inequality uses \sigma\le1/2.
To extend this estimate to the product, induct on |J|, starting with the constant functions when J is empty. Write g=a+b\chi_i, where a,b depend on the remaining coordinates, and use T for the operator on those coordinates as well. The one-coordinate estimate, applied pointwise, followed by the L^2 triangle inequality gives
This proves (2.3).
Let P_{\le k} be the orthogonal projection onto the span of \chi_A with |A|\le k. For every u in this span,
Taking the supremum of |\E[gu]| over unit L^2 vectors in this span, and applying Hölder’s inequality, therefore gives
These inequalities are valid for real k\ge0, with no rounding required.
Each nonempty Fourier support is counted at least once when summed over its coordinates. Using the difference identity and enlarging the resulting degree cutoff from k-1 to k, we obtain
Here each projection acts on the coordinates other than i, and \|\Delta_i h\|_{4/3}^2=I_i(h)^{3/2} because |\Delta_i h| is an indicator.
The function \sigma\log(4/\sigma) is increasing on (0,1/2] and is at most 2. Hence \rho^{-2k}\le m^{1/16}. If I(h)\le m^{1/4}, then I_i(h)^{1/2}\le m^{-3/8}, so (2.5) is at most \sigma^2m^{-5/16}I(h)\le m^{-1/4}I(h). If I(h)>m^{1/4}, the right side of (2.2) exceeds 1, whereas its left side is at most \Var_p(h)\le1/4.
3 Restriction to a vertex block
Return to a hypergraph property f on E=E_{n,r} and fix the bias p, with \sigma=\sqrt{p(1-p)}. Its Fourier coefficients use the basis of Section 2, with J=E. The restriction method of [9, Lemma 3.1 and Proposition 3.2] preserves a large permutation group after conditioning. We first obtain an averaged estimate for restricted Fourier degrees, and then relate those degrees to the sizes of the original supports.
For a vertex set B\subseteq[n], write
for the edge coordinates that remain free.
Lemma 3.1 (Averaged restriction estimate). Let r+1\le m\le n be integers and set k=\sigma\log m/64. For B chosen uniformly among the m-subsets of [n],
Proof. Fix B and an assignment y to the coordinates in E\setminus F_B. Denote the resulting Boolean function on F_B by f_y. Every permutation supported on B fixes each edge outside F_B individually, and consequently fixes y. Thus f_y is invariant under all these permutations, regardless of the assignment.
An edge with j vertices in B has an orbit of size \binom mj: its outside part is fixed and its inside part can be any j-subset of B. Since 1\le j\le r<m, this size is at least m. The free product measure is invariant under the same permutations, so influences are equal within each orbit. It follows that
Lemma 2.1 therefore applies to every f_y.
Average its conclusion over the product law of y. For A\subseteq F_B, the Fourier expansion of f gives
Orthonormality in the assigned coordinates yields
Also \E_y I_e(f_y)=I_{e,p}(f) for every e\in F_B, by conditioning the disagreement event. Consequently
Finally average over B. For each fixed edge e, a union bound on its r vertices gives \Pr_B(e\in F_B)\le rm/n, proving (3.1).
The next lemma extends the graph capture argument of [9, Lemma 3.3] to identify the hypergraph supports detected by this estimate. Here a support S is itself a set of distinct r-edges; its vertex union contains no isolated vertices.
Lemma 3.2 (Capturing a support at one vertex). Let n\ge r\ge3 and 1\le m\le n be integers, let k>0, and put
Suppose
For a uniform m-subset B of [n] and every S\subseteq E_{n,r} with 1\le|S|\le L,
Proof. Fix such an S, write s=|S|, and let V=\bigcup_{e\in S}e and v=|V|. Because s\le\binom vr\le v^r, the average degree of the hypergraph with edge set S is at most
Choose a vertex u\in V of degree d_S(u) between 1 and k. This choice depends only on S, before B is sampled.
Conditional on u\in B, each other vertex lies in B with probability (m-1)/(n-1). The union bound and v\le rs\le rL therefore give
On this event, the edges of S meeting B are exactly those containing u. Thus |S\cap F_B|=d_S(u)\in[1,k].
The captured set need not consist of a single edge: the block meets one support vertex, and retains every support edge incident with it. Also the vertex u may vary with S, since (3.3) is a separate probability bound for each nonnegative summand in (3.1).
Combining Lemmas 3.1 and 3.2 gives, whenever their hypotheses hold,
If L<1, this conclusion holds because the sum is empty. Otherwise, restrict the nonnegative sum in (3.1) to 1\le|S|\le L and divide by the lower bound m/(2n). This completes the transfer from restricted degree k to original degree (k/r)^{r/(r-1)}.
4 The uniform bound and its threshold consequence
We now choose the block size so that (3.4) controls the low-degree part of the variance. The weighted Parseval identity will control the remaining degrees.
Proof of Theorem 1.1. Fix r\ge3 and write \alpha=r/(r-1). Choose an integer N_r>r such that, for every n\ge N_r and m=\lfloor\sqrt n\rfloor,
Such an N_r exists: m is asymptotic to \sqrt n, and any fixed power of \log n grows more slowly than a positive power of n. In particular, the choice is independent of p and f.
Assume first that n\ge N_r, and set
Both cutoffs are positive. Since k/r\le\log n and
the third condition in (4.1) implies (3.2). Thus (3.4) and the fourth condition in (4.1) give
For the remaining degrees, (2.1) gives
The decisive bias dependence is
Indeed 2-\alpha=(r-2)/(r-1)>0, \sigma\le1, and \log m\ge(\log n)/3. This estimate remains valid at arbitrarily small positive \sigma. If L<1, the low-degree sum is empty and the same tail estimate bounds the whole variance.
Adding the two parts proves (1.1) for n\ge N_r with constant 2r+(192r)^\alpha. For r\le n<N_r, (2.1) gives \Var_p(f)\le\sigma^2 I_p(f)\le I_p(f)/4. Therefore a valid choice for all n and p is
We finish with the threshold consequence stated in the introduction. Recall that q(p)=\E_p f and p_a=\inf\{p\in[0,1]:q(p)\ge a\}.
Corollary 4.1. For a nontrivial increasing property of r-uniform hypergraphs on n\ge r vertices, where r\ge3, and every 0<\varepsilon<1/2,
Proof. The Margulis–Russo identity relates pivotal influences to the probability derivative; see [8], [10, Lemma 3], and [5, Lemma 2.2]. Here it follows directly by giving each coordinate its own bias: the expectation is affine in each bias separately, and its partial derivative in coordinate e is \E_p[f(x_{e\leftarrow1})-f(x_{e\leftarrow0})]. Monotonicity identifies this with I_{e,p}(f). Differentiating along the common bias gives q'(p)=I_p(f).
Nontrivial monotonicity gives q(0)=0 and q(1)=1. Some pair of configurations differing in one coordinate has different values, so its pivotal event has positive probability for every 0<p<1. Hence q'(p)>0 there, and the stated quantiles exist uniquely. Theorem 1.1 implies
Integrating from p_\varepsilon to p_{1-\varepsilon}, using the antiderivative \log(q/(1-q)), proves the claim.
References
- [1]W. Beckner, Inequalities in Fourier analysis, Annals of Mathematics 102 (1975), 159–182.
- [2]A. Bonami, Étude des coefficients de Fourier des fonctions de L^p(G), Annales de l’Institut Fourier 20 (1970), no. 2, 335–402.
- [3]J. Bourgain, J. Kahn, G. Kalai, Y. Katznelson, and N. Linial, The influence of variables in product spaces, Israel Journal of Mathematics 77 (1992), 55–64.
- [4]J. Bourgain and G. Kalai, Influences of variables and threshold intervals under group symmetries, Geometric and Functional Analysis 7 (1997), 438–461.
- [5]E. Friedgut and G. Kalai, Every monotone graph property has a sharp threshold, Proceedings of the American Mathematical Society 124 (1996), 2993–3002.
- [6]J. Kahn, G. Kalai, and N. Linial, The influence of variables on Boolean functions, in Proceedings of the 29th Annual Symposium on Foundations of Computer Science, IEEE, 1988, 68–80.
- [7]E. Kelman, G. Kindler, N. Lifshitz, D. Minzer, and M. Safra, Towards a proof of the Fourier-Entropy Conjecture?, Geometric and Functional Analysis 30 (2020), 1097–1138. See also arXiv:1911.10579v2, May 7, 2020.
- [8]G. A. Margulis, Probabilistic characteristics of graphs with large connectivity, Problems of Information Transmission 10 (1974), 174–179.
- [9]OpenAI, A Sharp Threshold Bound for Monotone Graph Properties, OpenAI Math Release preprint PDF, 2026. Reading view on this site: A Sharp Threshold Bound for Monotone Graph Properties.
- [10]L. Russo, On the critical percolation probabilities, Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 56 (1981), 229–237.