Influence and symmetric threshold widths

Source and verification

This article explains family 186 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Threshold location and transition width

A graph property on $n$ vertices is a Boolean function of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edge indicators invariant under every relabeling of the vertices. For an $r$-uniform hypergraph, the coordinates are the $r$-element vertex subsets. An increasing property remains true when edges are added.

Under independent Bernoulli-$p$ edges, write $q(p)={\mathbb{E}}_{p}f$. For a nontrivial increasing property, let $p_a$ be the density where its probability reaches $a$. Its transition width at tolerance $0<\epsilon <1/2$ is $p_{1-\epsilon }-p_{\epsilon }$.

This is an additive width in the parameter $p$. It differs from locating the midpoint $p_{1/2}$, and from bounding width relative to that midpoint.

🏷️ Pivotal influences and the two claims

An edge is pivotal when changing only that edge changes the value of $f$. Write $f_e^b(x)$ for the value with edge $e$ set to $b$, and define

$$\begin{array}{rl}{I}_{e,p}(f)& =\underset{p}{\mathrm{Pr}}(f_e^1(x)\ne f_e^0(x)),\\ I_p(f)& =\sum _e{I}_{e,p}(f).\end{array}$$

The probability is over the other coordinates. This convention includes no extra factor $p(1-p)$.

Manuscript claims

Every graph property, including nonmonotone ones, satisfies

$${\mathrm{Var}}_p(f)\le \frac{2^{17}}{(\log n{)}^2}{I}_p(f)$$

uniformly for $n\ge 2$ and $0<p<1$. For nontrivial increasing graph properties this yields

$$p_{1-\epsilon }-p_{\epsilon }\le \frac{2^{19}}{(\log n{)}^2}\log \frac{1}{2\epsilon }.$$

(OpenAI, 2026)

For every fixed uniformity $r\ge 3$, there is $C_r$ such that every $r$-uniform hypergraph property satisfies, for every $n\ge r$ and $0<p<1$,

$${\mathrm{Var}}_p(f)\le \frac{C_r}{(\log n{)}^{r/(r-1)}}{I}_p(f).$$

This also requires no monotonicity and is uniform in $p$. (OpenAI, 2026b)

Here $n$ counts vertices, not edge coordinates. With fixed $r$, their logarithms differ by only a constant factor asymptotically, but the convention matters for explicit constants.

🏷️ Integrating the influence inequality

For increasing Boolean functions, the Margulis–Russo identity gives $q^{\prime }(p)=I_p(f)$. Also ${\mathrm{Var}}_p(f)=q(p)(1-q(p))$. Thus a bound ${\mathrm{Var}}_p(f)\le C{I}_p(f)/L$ implies

$$q^{\prime }(p)\ge \frac{L}{C}q(p)(1-q(p)).$$

Integrating the derivative of $\log (q/(1-q))$ across the transition gives

$$p_{1-\epsilon }-p_{\epsilon }\le \frac{2C}{L}\log \frac{1-\epsilon }{\epsilon }.$$

Since $\log ((1-\epsilon )/\epsilon )\le 2\log (1/(2\epsilon ))$ for $0<\epsilon <1/2$, the graph constants give the stated quantile bound. This last inequality is equivalent to $4\epsilon (1-\epsilon )\le 1$ after exponentiating.

Monotonicity is used in this derivative step, not in the variance estimate. An influence bound for a nonmonotone property does not automatically define an increasing probability transition.

🏷️ Fourier mass and surviving symmetry

Use the orthonormal Fourier basis for Bernoulli-$p$ coordinates, and put ${\sigma }^2=p(1-p)$. If $\hat{f}(S)$ are its coefficients, then

$$\begin{array}{rl}{\mathrm{Var}}_p(f)& =\sum _{S\ne \varnothing }\hat{f}(S{)}^2,\\ {\sigma }^2{I}_p(f)& =\sum _S|S|\hat{f}(S{)}^2.\end{array}$$

Large Fourier degrees are controlled directly by influence. The difficulty is low-degree mass.

Choose a random block $B$ of about $\sqrt{n}$ vertices. Leave free all edges meeting $B$ and condition on every edge wholly outside it. Permutations within $B$ remain symmetries under every conditioning. Their free-edge orbits have many coordinates, so an elementary low-degree estimate applies to the restricted function.

The estimate is linear in restricted total influence. This permits averaging over the conditioned coordinates without a nonlinear loss. A restriction preserving only arbitrary edge-coordinate transitivity would not exploit the full vertex symmetry in this way.

🏷️ Turning low degrees into higher degrees

Regard a nonempty Fourier support $S$ as a graph or hypergraph. An $r$-uniform hypergraph with $s$ edges has a vertex of positive degree at most $r{s}^{(r-1)/r}$.

One way to see the scale is to let $v$ be its number of nonisolated vertices. Since $s\le v^r$, one has $v\ge s^{1/r}$; the minimum positive degree is at most the average $rs/v$, hence at most $r{s}^{(r-1)/r}$.

For $s\le (k/r{)}^{r/(r-1)}$, that degree is at most $k$. With probability comparable to $|B|/n$, the random block meets the support only at such a vertex, leaving between one and $k$ support edges free. The expected restricted influence carries the same factor $|B|/n$, so those factors cancel.

Taking $k$ proportional to $\sigma \log n$ controls original Fourier degrees up to $L\asymp (\sigma \log n{)}^{r/(r-1)}$. The remaining mass is at most ${\sigma }^2{I}_p(f)/L$. Its coefficient contains

$${\sigma }^{2-r/(r-1)}(\log n{)}^{-r/(r-1)},$$

which is uniformly bounded by the required logarithmic factor. For graphs the exponent of $\sigma$ is zero; for $r\ge 3$ it is positive. The source handles small-parameter ranges separately to keep the result uniform for all $p$.

🏷️ Key steps and proof outlines

Derivatives turn a norm inequality into low-degree control

For a Boolean function $h$, define the coordinate difference ${\Delta }_{i}h=h(x_{i\leftarrow 1})-h(x_{i\leftarrow 0})$. It takes values in $\{-1,0,1\}$, so $\Vert {\Delta }_{i}h{\Vert }_{4/3}^2=I_i(h{)}^{3/2}$. With $\sigma =\sqrt{p(1-p)}$, the normalized Fourier coefficients satisfy

$$\hat{h}(A\cup \{i\})=\sigma \widehat{{\Delta }_{i}h}(A).$$

This identity accounts for the precise bias factor in the influence formula. It does not use monotonicity. (OpenAI, 2026b)

The analytic lemma starts with the noise operator $T{\chi }_A={\rho }^{|A|}{\chi }_A$, where $\rho =\sigma /4$. Expanding $(a+\rho b{\chi }_i{)}^4$ and using $|\mathbb{E}{\chi }_i^3|\le 1/\sigma$ and $\mathbb{E}{\chi }_i^4\le 1/{\sigma }^2$ proves the one-coordinate bound $\Vert Tg{\Vert }_4\le \Vert g{\Vert }_2$. Induction on coordinates, writing $g=a+b{\chi }_i$ and applying the triangle inequality to $(Ta{)}^2+(Tb{)}^2$, extends it to the whole product space.

If $P_{\le k}$ is projection onto Fourier degrees at most $k$, duality and Hölder give

$$\Vert P_{\le k}g{\Vert }_2\le {\rho }^{-k}\Vert g{\Vert }_{4/3}.$$

Sum this estimate over coordinate differences. Every nonempty Fourier support is counted at least once, yielding

$$\sum _{1\le |S|\le k}\hat{h}(S{)}^2\le {\sigma }^2{\rho }^{-2k}\sum _i{I}_i(h{)}^{3/2}.$$

Assume $I_i(h)\le I(h)/m$ and set $k=\sigma \log m/64$. Since $\sigma \log (4/\sigma )\le 2$, the noise loss obeys ${\rho }^{-2k}\le m^{1/16}$. If $I(h)\le m^{1/4}$, every $I_i(h{)}^{1/2}\le m^{-3/8}$, giving the desired bound $m^{-1/4}I(h)$. If $I(h)>m^{1/4}$, that right side exceeds one while the Fourier mass is at most $1/4$. This two-case argument keeps the final estimate linear in total influence.

Conditioning preserves exactly the symmetry that is needed

Let $B$ contain $m$ vertices and let $F_B$ be the hyperedges meeting it. Fix every coordinate outside $F_B$. A permutation supported on $B$ fixes that entire conditioning, so the restricted function $f_y$ remains symmetric under those permutations. An edge with $j$ vertices in $B$ has an orbit of size $\left(\genfrac{}{}{0ex}{}{m}{j}\right)\ge m$, provided $m\ge r+1$. Equal influences within each orbit give $I_e(f_y)\le I(f_y)/m$.

There is no need to compare Fourier coefficients pointwise across restrictions. Instead,

$$\widehat{f_y}(A)=\sum _{D\subseteq E\setminus F_B}\hat{f}(A\cup D){\chi }_D(y).$$

After squaring and averaging over $y$, orthogonality removes every cross term. Averaging restricted influences is also exact, because it just conditions the pivotal event. Thus

$$\sum _S\underset{B}{\mathrm{Pr}}(1\le |S\cap F_B|\le k)\hat{f}(S{)}^2\le m^{-1/4}\frac{rm}{n}{I}_p(f).$$

Capture one vertex, then cancel the sampling probability

Put $\alpha =r/(r-1)$ and $L=(k/r{)}^{\alpha }$. A support with $s\le L$ edges has a vertex $u$ of positive degree at most $k$. Its vertex union has at most $rL$ members. Conditional on $u\in B$, a union bound gives

$$\mathrm{Pr}(B\cap V(S)=\{u\})\ge \frac{m}{n}\left(1-rL\frac{m-1}{n-1}\right)\ge \frac{m}{2n},$$

when the parenthesized loss is at most $1/2$. On this event the retained support consists precisely of the edges incident with $u$. Dividing the averaged estimate by $m/(2n)$ bounds the original low-degree mass by $2r{m}^{-1/4}{I}_p(f)$.

For $m=\lfloor \sqrt{n}\rfloor$, the remaining Fourier degrees cost at most ${\sigma }^2{I}_p(f)/L$. Here ${\sigma }^2/L$ is proportional to ${\sigma }^{2-\alpha }(\log m{)}^{-\alpha }$; the exponent is nonnegative, including the graph case $\alpha =2$. If $L<1$, the low-degree part is empty and the same tail estimate already bounds everything. Finitely many small $n$ are absorbed using ${\mathrm{Var}}_p(f)\le I_p(f)/4$. These steps explain uniformity even near $p=0$ or $1$, rather than assuming the bias stays bounded away from the endpoints. The graph paper develops the corresponding graph restriction argument; the companion’s Fourier, restriction, and completion sections make the hypergraph dependence explicit. (OpenAI, 2026a)

See Also

• Covering thresholds and Graph expectation thresholds concern threshold location, not transition width.
• Boolean Fourier degree uses the same Fourier language for a different comparison between linear coefficients and polynomial degree.

🏷️ Manuscripts and verification scope

• A uniform influence bound for hypergraph properties — pinned manuscript and companion source.
• A Sharp Threshold Bound for Monotone Graph Properties — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page selects only the monotone graph quantile-width bound. It does not document the nonmonotone variance bound or the hypergraph companion. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. A Sharp Threshold Bound for Monotone Graph Properties.

🐻  OpenAI 2026b. A uniform influence bound for hypergraph properties.