Uniform influence and sharp thresholds for graph and hypergraph properties

1 · The essentials

Some properties of a network can become much more likely when the chance of including each connection increases only a little. These manuscripts study properties that do not change when the points are renamed. For properties that cannot be lost by adding connections, they bound how much that chance must increase to move from a low probability of having the property to a high one. The graph manuscript shows that this interval shrinks at least as fast as a constant times $1/ (lo g n)^{2}$ , where $n$ is the number of points. The main manuscript treats connections joining a fixed number of points, rather than just two, and gives a corresponding bound. Its underlying estimate also applies to properties that can be lost when connections are added. The main result has a Lean formalization, although the supplied information does not specify its detailed coverage.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine turning a dial that makes more connections appear in a network: a qualifying property moves from unlikely to likely within a short stretch of the dial. The results bound the length of that stretch, not where it lies, and require that renaming the points makes no difference.

Why it matters

The manuscripts describe these bounds as resolving the graph and fixed-uniformity hypergraph threshold-width conjectures of Friedgut and Kalai. The main manuscript also supplies an influence estimate that holds across the entire range of connection probabilities and does not require the property to be increasing.

2 · Going further

The graph problem concerns a nontrivial increasing Boolean property of graphs on $n \geq 2$ vertices, invariant under every permutation of the vertices. Here increasing means that adding edges cannot destroy the property. For fixed $0 < ε < 1/2$ , let $p_{ε}$ and $p_{1 - ε}$ be the edge probabilities at which the property has probability $ε$ and $1 - ε$ . The graph manuscript shows that $p_{1 - ε} - p_{ε} \leq C lo g (1/ (2 ε)) / (lo g n)^{2}$ , with a universal constant $C$ .

The main manuscript instead considers simple $r$ -uniform hypergraphs, whose edges each contain exactly $r$ vertices, for fixed integer $r \geq 3$ . Its central estimate is $Var_{p} (f) \leq C_{r} I_{p} (f) / (lo g n)^{r / (r - 1)}$ for every relabeling-invariant Boolean property $f$ . Here $Var_{p} (f)$ measures the variability of the yes-or-no outcome, and $I_{p} (f)$ is its total influence, measuring aggregate sensitivity to changes in individual edges. The constant depends only on $r$ , and the estimate is uniform over $0 < p < 1$ , even without monotonicity.

The route described in the main abstract is to obtain a threshold-width bound from this influence estimate when the property is increasing. For fixed $ε$ , the resulting width is $O_{r} ((lo g n)^{- r / (r - 1)})$ . The abstracts do not give further details of the argument. The companion graph manuscript supplies the corresponding exponent $2$ for graphs; together, the manuscripts describe resolutions of the Friedgut–Kalai threshold-width conjectures in these two settings.

Useful notions

Graphs and edges
Hypergraphs with fixed edge size
Probability of a yes-or-no event
Increasing properties
Logarithms and asymptotic bounds

What was known before / what is new

Before

The source identifies the target bounds as threshold-width conjectures of Friedgut and Kalai. It does not describe earlier quantitative bounds or the history of progress toward these conjectures.

New

The main manuscript gives a uniform influence bound for relabeling-invariant properties of fixed-uniformity hypergraphs, including nonmonotone properties. For increasing properties, it yields the stated hypergraph threshold-width bound. The companion manuscript shows the graph bound with explicit dependence on $ε$ through $lo g (1/ (2 ε))$ .

Limits and assumptions

Relabeling invariance is essential to the stated hypotheses. The threshold conclusions require nontrivial increasing properties and $0 < ε < 1/2$ ; the influence estimate does not require increasingness. In the main manuscript, $r \geq 3$ is fixed, the hypergraphs are simple, and the constant may depend on $r$ . These are bounds on transition width, not formulas for transition location. The main result has a Lean formalization, but the supplied material does not specify exactly which claims it covers, so formal verification is not asserted here for every companion or derived claim. The source identifies no further open problems.

Mini glossary

Relabeling-invariant property: A property whose truth does not change when the vertices are renamed.
Increasing property: A property that cannot be destroyed by adding edges.
Simple r-uniform hypergraph: A collection of distinct edges, each consisting of exactly r vertices.
Threshold width: The difference between the edge probabilities at which a property has probability ε and 1−ε.
Total influence: The sum over edges of the probabilities that changing an edge's presence changes the property's yes-or-no outcome.
Variance: For a Boolean property with probability q of holding, its variance is q(1−q).

Keywords : Sharp thresholds · Total influence · Hypergraph properties

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

Proves the Friedgut–Kalai threshold-width conjectures for graphs and fixed-uniformity hypergraphs. For fixed $0 < ε < 1/2$ , every nontrivial increasing relabeling-invariant property crosses from probability ε to $1 - ε$ within width $O ((lo g n)^{- 2})$ for graphs and $O_{r} ((lo g n)^{- r / (r - 1)})$ for r-uniform hypergraphs, r ≥ 3. The hypergraph influence bound also applies to nonmonotone properties.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/186.md

Manuscripts in this family

★

A uniform influence bound for hypergraph properties

05/10/2026

To be verified

For every fixed integer r ≥ 3, we prove that every relabeling-invariant Boolean property of simple r-uniform hypergraphs on n vertices satisfies $Var_{p} (f) \leq C_{r} I_{p} (f) / (lo g n)^{r / (r - 1)}$ . The constant depends only on r, and the bound holds uniformly for all $0 < p < 1$ without a monotonicity assumption. For increasing properties, it gives the corresponding threshold-width bound with exponent $r / (r - 1)$ , proving the hypergraph threshold-width conjecture of Friedgut and Kalai.

PDF GitHub folder

A Sharp Threshold Bound for Monotone Graph Properties

25/09/2026

To be verified

We prove the Friedgut–Kalai sharp-threshold conjecture. For every integer n ≥ 2, every nontrivial increasing family of graphs on n vertices invariant under all vertex permutations, and every $0 < ε < 1/2$ , the edge probabilities at which its probability equals ε and $1 - ε$ differ by at most $C lo g (1/ (2 ε)) / (lo g n)^{2}$ , for a universal constant C.

PDF GitHub folder