How narrow must a symmetric random-graph transition be

← All digests

Family 186 · Combinatorics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

As the edge probability of a random graph increases, a property such as connectivity changes from unlikely to likely. How wide can that transition be if the property treats every vertex label equally and is preserved when edges are added?

This question concerns the width of the transition, not where it occurs. A theorem locating the threshold near a counting prediction does not automatically determine how rapidly the probability rises through that location.

The two manuscripts claim optimal-order universal width bounds for graphs and the conjectured extension to uniform hypergraphs. M2 gives a squared logarithm in the denominator for graphs. M1 gives exponent $r/(r-1)$ for $r$-uniform hypergraphs. Both are driven by stronger sensitivity estimates that hold at every edge probability, even for properties that are not increasing.

2. Background and essential definitions

In $G(n,p)$, each possible edge among $n$ vertices is present independently with probability $p$. A graph property is a yes-or-no rule unchanged by every permutation of the vertex labels. Connectivity and containing a triangle are examples.

Write the rule as a Boolean function $f$, taking values zero or one. It is increasing if adding edges cannot change a yes to a no. For a nontrivial increasing property, let

$$q(p)=\mathbb E_p f, \qquad p_a=\inf\{p:q(p)\geq a\}.$$

The quantile $p_a$ is the density at which the probability reaches level $a$. For $0<\varepsilon<1/2$, the transition width is

$$p_{1-\varepsilon}-p_\varepsilon.$$

An edge is pivotal for the other edges’ configuration when forcing it present rather than absent changes the property. Its influence is

$$I_{e,p}(f)=\Pr_p\bigl(f(x^{e\leftarrow1}) \ne f(x^{e\leftarrow0})\bigr),$$

and total influence is $I_p(f)=\sum_e I_{e,p}(f)$. The probability is over the other coordinates. This convention includes no extra factor $p(1-p)$.

For a Boolean function, the variance is $\operatorname{Var}_p(f)=q(p)(1-q(p))$. It is substantial when the outcome is uncertain and small when the property is almost certain or almost impossible.

An $r$-uniform hypergraph replaces ordinary edges by $r$-element vertex subsets. Each possible hyperedge is independently present with probability $p$. A hypergraph property again ignores vertex labels. Throughout, $n$ counts vertices, not the $\binom nr$ edge coordinates, and logarithms are natural.

3. Development history and previous partial results

Kahn, Kalai and Linial established a fundamental connection between Boolean Fourier analysis and influence. For a function with transitive coordinate symmetry, this forces total influence to grow logarithmically with the number of coordinates when the variance is bounded below. Bourgain, Kahn, Kalai, Katznelson and Linial extended the influence method to product probability spaces.

Friedgut and Kalai’s 1996 theorem used such estimates to prove narrow transitions for increasing properties with transitive symmetry. For graph properties, this gives a universal width of order $1/\log n$ for fixed probability levels.

They conjectured the stronger graph bound $1/(\log n)^2$. Vertex relabeling supplies more information than the fact that all individual edges are equivalent: it also constrains how groups of edges overlap. Exploiting that richer action is the source of the additional logarithm.

Bourgain and Kalai approached the conjectured exponent. For every fixed $\eta>0$, they obtained graph widths of order $(\log n)^{-2+\eta}$. For $r$-uniform hypergraphs, their influence estimates at the unbiased density $p=1/2$ approach exponent $r/(r-1)$ with an arbitrary fixed loss.

Kelman, Kindler, Lifshitz, Minzer and Safra obtained, for graph properties at $p=1/2$, total influence at least a constant times

$$\operatorname{Var}_{1/2}(f) \frac{(\log n)^2}{(\log\log n)^2}.$$

The present manuscripts claim to remove the remaining losses and to keep the estimates uniform throughout $0<p<1$. That uniformity is needed for a general width theorem, since a property’s transition need not occur near one half.

4. What the new manuscripts claim

M2: graph properties

For every vertex-relabeling-invariant Boolean graph property, whether increasing or not, M2 states

$$\operatorname{Var}_p(f) \leq\frac{2^{17}}{(\log n)^2}I_p(f) \qquad(0<p<1).$$

For a nontrivial increasing property, it deduces

$$p_{1-\varepsilon}-p_\varepsilon \leq\frac{2^{19}}{(\log n)^2} \log\frac1{2\varepsilon}.$$

The numerical constants are convenient explicit choices, not optimized ones. The theorem is uniform over all $n\geq2$, all such properties and all $0<\varepsilon<1/2$.

M1: uniform hypergraphs

For each fixed $r\geq3$, M1 claims a constant $C_r$ such that every relabeling-invariant Boolean property of simple $r$-uniform hypergraphs satisfies

$$\operatorname{Var}_p(f) \leq\frac{C_r}{(\log n)^{r/(r-1)}}I_p(f) \qquad(n\geq r,\ 0<p<1).$$

Again, monotonicity is unnecessary for this variance–influence inequality. For a nontrivial increasing property, the stated consequence is

$$p_{1-\varepsilon}-p_\varepsilon \leq\frac{2C_r}{(\log n)^{r/(r-1)}} \log\frac{1-\varepsilon}{\varepsilon}.$$

For fixed $\varepsilon$, this is the conjectured $(\log n)^{-r/(r-1)}$ width scale. M1 reproduces the graph companion’s analytic restriction argument and adds the combinatorial estimate needed for hyperedge supports.

These are additive widths in the probability parameter $p$. They do not assert that the width divided by the threshold location tends to zero for every property.

5. Why the advance matters

Importance: 4/5. The claims settle broad quantitative sharp-threshold questions using only vertex symmetry and monotonicity, without a detailed description of the property.

For graphs, the squared-logarithm order is optimal in general at fixed probability levels. Friedgut and Kalai already noted examples involving cliques of order proportional to $\log n$ whose widths have this scale. Some familiar properties have much narrower transitions, but a universal theorem must accommodate the worst case.

The stronger influence statement also has independent meaning. A symmetric property whose answer remains uncertain must have many opportunities for a single edge to change that answer. This conclusion survives without monotonicity, although a nonmonotone property need not have one increasing transition to which the width language applies.

The rating reflects the sharp universal graph order, the hypergraph extension and the full-density control. It is distinct from the threshold-location advances in nearby families, which compare where a transition sits with expectation-based predictions.

6. The main idea

Split variation into Fourier degrees

A function of independent edge bits has an orthogonal expansion indexed by edge subsets $S$. Under Bernoulli density $p$, one uses centered, normalized coordinate functions so that the basis remains orthonormal.

If $\widehat f(S)$ denotes a coefficient, the basic identities are

$$\operatorname{Var}_p(f)=\sum_{S\ne\varnothing}\widehat f(S)^2, \qquad p(1-p)I_p(f)=\sum_S|S|\widehat f(S)^2.$$

The second sum weights large supports more heavily. Consequently, influence already controls the high-degree part of the variance. The problem is bounding mass on smaller edge subsets.

Restrict through vertices, preserving symmetry

Choose a random block $B$ of about $\sqrt n$ vertices. Keep every edge touching $B$ free and fix all edges entirely outside it.

Every permutation within $B$ still preserves the restricted function. Each free edge belongs to a large orbit under these surviving permutations, so no individual conditional influence can dominate the total. An elementary Fourier estimate then controls the restricted low-degree mass, with a bound linear in total influence.

Linearity matters because the proof averages over the fixed outside configuration and over the random block. A nonlinear loss at that stage could spoil the desired uniform estimate.

Regard a Fourier support as a small graph

An edge set $S$ indexing a coefficient is itself a graph. If it has at most $k^2/2$ edges, it has a nonisolated vertex of degree at most $k$.

With sufficient probability, the random block meets the support only at that vertex. The restriction then retains between one and $k$ edges of $S$. Thus a low-degree bound after restriction controls original Fourier supports up to a quadratic degree scale. This is where the graph’s squared logarithm enters.

For an $r$-uniform support with $s$ edges, the analogous combinatorial observation gives a vertex of positive degree at most $rs^{(r-1)/r}$. Inverting that relationship produces the exponent $r/(r-1)$ in the original support size.

The proof tracks the factor $\sqrt{p(1-p)}$ in the Fourier cutoff. In the final combination of low- and high-degree estimates, the bias dependence cancels or remains bounded. This permits densities arbitrarily close to zero or one.

Integrate sensitivity into a width bound

For increasing properties, the Margulis–Russo identity gives

$$q'(p)=I_p(f).$$

The variance inequality therefore bounds $q'(p)$ below by a multiple of $q(p)(1-q(p))$ times the relevant logarithmic power. Integrating the derivative of $\log(q/(1-q))$ between the two quantiles yields the stated width estimates. This final step is why monotonicity is needed for the transition conclusion but not for the underlying sensitivity theorem.

7. Scope, limitations, and open questions

The symmetry is invariance under all vertex relabelings. A property singling out a distinguished vertex, edge or labeled pattern need not satisfy the same estimate. Mere transitivity of arbitrary coordinates supplies a weaker general framework.

Hypergraph uniformity $r$ is fixed, and its constant may depend on $r$. The claim is not uniform when hyperedge size grows with the number of vertices.

The width bound is additive. If a threshold lies at a much smaller density than $(\log n)^{-2}$, the universal graph estimate may say little about its relative sharpness or precise transition window. Determining exact locations, leading constants and limiting probability curves remains property-specific.

The manuscripts do not use the integral–fractional comparison or the second Kahn–Kalai theorem in families 175 and 176. Those concern threshold locations; this family’s restriction and influence argument addresses widths directly. Nor does the result settle every broader conjecture about Boolean Fourier coefficients, such as the general Fourier–entropy conjecture.

8. Sources and further reading

M2 gives the graph theorem and the density-uniform variance bound. M1, dated October 5, extends the restriction argument to hypergraphs and derives its quantile inequality.

The central historical source is Friedgut–Kalai’s sharp-threshold paper. Kelman–Kindler–Lifshitz–Minzer–Safra supplies a recent symmetry-sensitive Fourier predecessor. The manuscripts’ bibliographies identify the Kahn–Kalai–Linial influence theorem, Bourgain–Kalai’s group-symmetry refinements, and the Margulis–Russo derivative identity used in the final integration.

Source manuscripts

• M1. OpenAI, A uniform influence bound for hypergraph properties (October 5, 2026).
• M2. OpenAI, A Sharp Threshold Bound for Monotone Graph Properties (September 25, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.