# Reading roadmap: A uniform influence bound for hypergraph properties

The proof combines biased Fourier identities, restriction to a vertex block, and a bound on captured low-degree mass. It chooses a block and cutoff to combine this with the Fourier tail uniformly in the bias, and then integrates the influence bound for increasing properties.

Source SHA-256: `cc2f0b74e1ebd11c094d2ece95e4b277f0a521eb4a7f5f20ddb00b230285ba1f`. Indexed 23,156 characters.

Edges point from prerequisite to consumer. Solid proof edges are attributed inferences, not formal certificates; references remain candidates.

## Internal claim index

### Theorem 1.1 — `thm:main`

Source lines 61–70.

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\}$, \Var_p(f)\le \frac{C_r}{(\log n)^{r/(r-1)}}I_p(f). No monotonicity assumption is required.

*Extractive statement; proof gist not independently reconstructed.*

Proof opening: 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$, m\ge r+1,\qquad \log m\ge\tfrac13\log n,\\ r(\log n)^\alpha n^{-1/2}\le\tfrac12,\qquad m^{-1/4}(\log n)^\alpha\le1. 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 \[ \sigma=\sqrt{p(1-p)},\qquad k=\frac{\sigma\log m}{64},\qquad L=(k/r)^\alpha. \] Both cutoffs are positive. Since $k/r\le\log n$ and \[ \frac{m-1}{n-1}\le\frac{\sqrt n-1}{n-1} =\frac1{\sqrt n+1}\le n^{-1/2}, \] the third con


Candidate references: `eq:large-n` (candidate_proof_dependency); `eq:capture-condition` (candidate_proof_dependency); `eq:captured-mass` (candidate_proof_dependency); `eq:parseval` (candidate_proof_dependency); `eq:main` (candidate_proof_dependency).

### Lemma 2.1 — `lem:low`

Source lines 206–215.

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 \sum_{1\le |S|\le k}\widehat h(S)^2\le m^{-1/4}I(h). The sum is empty when $k<1$.

*Extractive statement; proof gist not independently reconstructed.*

Proof opening: 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 \|Tg\|_4\le\|g\|_2 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 \E(a+\rho b\chi_i)^4 &\le a^4+6\rho^2a^2b^2+ \frac{2\rho^3}{\sigma}(a^2b^2+b^4) +\frac{\rho^4}{\sigma^2}b^4\\ &=a^4+\frac{13\sigma^2}{32}a^2b^2 +\frac{9\sigma^2}{256}b^4 \le(a^2+b^2)^2, where the last inequality uses $\sigma\le1/2$. To


Candidate references: `eq:24` (candidate_proof_dependency); `eq:derivative-mass` (candidate_proof_dependency); `eq:low` (candidate_proof_dependency).

### Lemma 3.1 — `lem:block`

Source lines 309–318.

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]$, \sum_{S\subseteq E} \Pr_B(1\le|S\cap F_B|\le k)\widehat f(S)^2 \le m^{-1/4}\frac{rm}{n}I_p(f).

*Extractive statement; proof gist not independently reconstructed.*

Proof opening: 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 \[ I_e(f_y)\le I(f_y)/m\qquad(e\in F_B). \] Lemma~\ref{lem:low}


Candidate references: `lem:low` (candidate_proof_dependency); `eq:block` (candidate_proof_dependency).

### Lemma 3.2 — `lem:capture`

Source lines 363–378.

Capturing a support at one vertex

Let $n\ge r\ge3$ and $1\le m\le n$ be integers, let $k>0$, and put \[ \alpha=\frac r{r-1},\qquad L=(k/r)^\alpha. \] Suppose rL\frac{m-1}{n-1}\le\frac12. For a uniform $m$-subset $B$ of $[n]$ and every $S\subseteq E_{n,r}$ with $1\le|S|\le L$, \Pr_B(1\le|S\cap F_B|\le k)\ge\frac{m}{2n}.

*Extractive statement; proof gist not independently reconstructed.*

Proof opening: 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 \[ \frac{rs}{v}\le r s^{(r-1)/r}\le k. \] 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 \Pr_B(B\cap V=\{u\}) &\ge\frac mn\left(1-(v-1)\frac{m-1}{n-1}\right)\\ &\ge\frac m{2n}. 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]$.

### Corollary 4.1 — `cor:threshold`

Source lines 493–502.

For a nontrivial increasing property of $r$-uniform hypergraphs on $n\ge r$ vertices, where $r\ge3$, and every $0<\varepsilon<1/2$, \[ p_{1-\varepsilon}-p_\varepsilon \le\frac{2C_r}{(\log n)^{r/(r-1)}} \log\frac{1-\varepsilon}{\varepsilon}. \]

*Extractive statement; proof gist not independently reconstructed.*

Proof opening: The Margulis--Russo identity relates pivotal influences to the probability derivative; see~\cite{Margulis74}, \cite[Lemma~3]{Russo81}, and \cite[Lemma~2.2]{FK96}. 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$ ther


Candidate references: `thm:main` (candidate_proof_dependency); `external:Margulis74` (external_reference); `external:Russo81` (external_reference); `external:FK96` (external_reference).

## External inputs and references

### [1] Beckner75 — `external:Beckner75`

Source lines 534–538.

W. Beckner, Inequalities in Fourier analysis, Annals of Mathematics 102 (1975), 159--182.


Candidate references: `sec:fourier` (external_reference).

### [2] Bonami70 — `external:Bonami70`

Source lines 538–543.

A. Bonami, \'{E}tude des coefficients de Fourier des fonctions de $L^p(G)$, Annales de l'Institut Fourier 20 (1970), no.~2, 335--402.


Candidate references: `sec:fourier` (external_reference).

### [3] BKKKL92 — `external:BKKKL92`

Source lines 543–548.

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.


Candidate references: `sec:introduction` (external_reference).

### [4] BK97 — `external:BK97`

Source lines 548–553.

J. Bourgain and G. Kalai, Influences of variables and threshold intervals under group symmetries, Geometric and Functional Analysis 7 (1997), 438--461.


Candidate references: `sec:introduction` (external_reference).

### [5] FK96 — `external:FK96`

Source lines 553–558.

E. Friedgut and G. Kalai, Every monotone graph property has a sharp threshold, Proceedings of the American Mathematical Society 124 (1996), 2993--3002.


Candidate references: `sec:introduction` (external_reference); `cor:threshold` (external_reference).

### [6] KKL88 — `external:KKL88`

Source lines 558–563.

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.


Candidate references: `sec:introduction` (external_reference).

### [7] KKLMS20 — `external:KKLMS20`

Source lines 563–569.

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.


Candidate references: `sec:introduction` (external_reference).

### [8] Margulis74 — `external:Margulis74`

Source lines 569–574.

G. A. Margulis, Probabilistic characteristics of graphs with large connectivity, Problems of Information Transmission 10 (1974), 174--179.


Candidate references: `cor:threshold` (external_reference).

### [9] Graph2026 — `external:Graph2026`

Source lines 574–580.

OpenAI, A Sharp Threshold Bound for Monotone Graph Properties, OpenAI Math Release preprint \href{https://github.com/openai/math/blob/main/preprints/A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties-September-25-2026/paper.pdf}{OAI:A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties-September-25-2026}, 2026.


Candidate references: `sec:introduction` (external_reference); `sec:fourier` (external_reference); `sec:restriction` (external_reference).

### [10] Russo81 — `external:Russo81`

Source lines 580–585.

L. Russo, On the critical percolation probabilities, Zeitschrift f\"ur Wahrscheinlichkeitstheorie und verwandte Gebiete 56 (1981), 229--237.


Candidate references: `cor:threshold` (external_reference).

## Coverage and limits

{"mode": "native_latex_index", "claims": 5, "sections": 4, "external_references": 10, "source_bibliography_entries": 10, "unresolved_bibliography": 0, "unresolved": 0}

- Reference edges are not certified proof dependencies. Edge direction is prerequisite → consumer.
- Numbers reflect simple source counters; labels and line anchors are authoritative.
- Extractive statements and proof openings are marked; they are not reconstructed proof gists.
- Macros, included files and custom counters require an expanded source or annotated fallback.