Search

Uniform influence and sharp thresholds for graph and hypergraph properties

Every symmetric increasing graph property switches on within a window of width about 1/(log n)².

2 papers September 25, 2026 Explained by AI

Draw each possible edge of a graph with probability p. A property that survives adding edges switches from rare to common as p grows. Friedgut and Kalai showed the switch happens within a window of width about 1/log n. This work proves their conjecture that the window is about 1/(log n)², and claims the hypergraph version too.

First step
—
Significance
Major
It settles the Friedgut–Kalai sharp-threshold conjecture from 1996, the best possible order in n.
Trust
Formal proof listed
Field
Combinatorics
2 papers

The explanation

Take four dots and the six possible lines between them. Draw each line with probability p, independently. What is the chance that at least one line appears? It is 1 − (1 − p)⁶. That chance reaches 10% when p is about 0.017. It reaches 90% when p is about 0.319. So the switch from unlikely to likely happens over a window about 0.30 wide.

This is a random graph: dots, called vertices, joined by random lines, called edges. "Has at least one edge" is a graph property. It does not care how the dots are labelled. It is also increasing: adding edges can never destroy it. The window where its chance climbs from ε to 1 − ε is its threshold width. Here ε is a small fixed number, such as 0.1.

With many vertices, these windows get narrow. In 1996, Friedgut and Kalai showed a universal limit. For any such property on n vertices, the width is at most a constant times log(1/(2ε))/log n. They conjectured that log n could be replaced by its square, (log n)². That would mean much sharper switches. The square would be the best possible order. A property like containing a group of about log n vertices all joined to each other has a window that small. Bourgain and Kalai later came within any small margin of the square.

The graph paper proves the conjecture. For every n of at least 2, the width is at most 2¹⁹ log(1/(2ε))/(log n)². The paper calls this constant a convenient explicit choice. It is large. With ε = 0.1, the bound drops below 1 only once log n passes about 919. So the value lies in the order, (log n)², not in the number.

The difficulty was using symmetry well. Friedgut and Kalai used only that relabelling can move any edge onto any other. That fact alone gives one factor of log n. The paper uses relabellings more directly. It picks a random block of about √n vertices and frees every edge that touches it. All other edges are fixed. Shuffling the block's vertices still leaves the property unchanged. The paper builds its sharper estimate on that surviving symmetry.

A companion paper extends this to hypergraphs. There an edge joins r vertices instead of two, for a fixed r of 3 or more. Friedgut and Kalai conjectured a width of order (log n) to the power −r/(r−1). The hypergraph paper claims to prove that bound. Its main inequality does not need the property to be increasing. For graphs, the analogous exponent would be 2, matching the square above.

How sure is this? A computer proof checker called Lean has checked the graph result. The Lean scope note states the width bound for every n of at least 2, every such property, and every ε between 0 and 1/2. The hypergraph paper is outside that check. No specialist review of either paper has been published.

What it doesn't show. This does not give a small explicit constant; the stated factor 2¹⁹ makes the bound useful only for enormous graphs.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Major if it holds. Lean has checked the graph theorem; the hypergraph extension is not checked, and no specialist review is published.

Words used

Random graph
Vertices with each possible edge drawn independently with the same probability p.
Graph property
A yes-or-no feature of a graph that does not depend on how vertices are labelled.
Increasing property
A property that can never be destroyed by adding edges.
Threshold width
How much p must rise for the property's chance to climb from ε to 1 − ε.
Hypergraph
Like a graph, but each edge joins a fixed number r of vertices.
Influence
How often changing one edge changes whether the property holds.

The original papers (2)

Lean notes

All quoted lines (11)
  1. For graph properties, vertex permutations act transitively on the edge coordinates, and their theorem gives the universal width bound Clog⁡(1/(2ε))/log⁡nC\log(1/(2\varepsilon))/\log n.
    A Sharp Threshold Bound for Monotone Graph Properties Back to text
  2. They conjectured the denominator (log⁡n)2(\log n)^2 with the same dependence on ε\varepsilon.
    A Sharp Threshold Bound for Monotone Graph Properties Back to text
  3. The squared logarithm is the optimal order in nn when ε\varepsilon is fixed.
    A Sharp Threshold Bound for Monotone Graph Properties Back to text
  4. Friedgut and Kalai already pointed to the property of containing a clique with order proportional to log⁡n\log n: its transition width can be of order (log⁡n)−2(\log n)^{-2}.
    A Sharp Threshold Bound for Monotone Graph Properties Back to text
  5. Thus their result approached the conjectured exponent arbitrarily closely.
    A Sharp Threshold Bound for Monotone Graph Properties Back to text
  6. Theorem … resolves that conjecture positively; its numerical constant is only a convenient explicit choice.
    A Sharp Threshold Bound for Monotone Graph Properties Back to text
  7. Here the restriction is chosen through the vertices: leave free all edges touching a random block BB of about n\sqrt n vertices, while conditioning on every other edge.
    A Sharp Threshold Bound for Monotone Graph Properties Back to text
  8. Permutations inside BB survive every such conditioning.
    A Sharp Threshold Bound for Monotone Graph Properties Back to text
  9. Friedgut and Kalai conjectured that this width is at most Or,ε((log⁡n)−r/(r−1))O_{r,\varepsilon}((\log n)^{-r/(r-1)}) for every increasing rr-uniform hypergraph property.
    A uniform influence bound for hypergraph properties Back to text
  10. Corollary … proves this conjectured bound by integrating (…), with an explicit dependence on ε\varepsilon.
    A uniform influence bound for hypergraph properties Back to text
  11. No monotonicity assumption is required.
    A uniform influence bound for hypergraph properties Back to text

Other sources

  1. openai/math, Lean scope note for family 186 (2026) the formalization proves that the edge-probability interval between probabilities ε\varepsilon and 1−ε1-\varepsilon has width at most 219log⁡(1/(2ε))/(log⁡n)22^{19}\log(1/(2\varepsilon))/(\log n)^2.
  2. openai/math release notes (2026): model provenance and review status manuscripts and supporting proof artifacts produced by an internal OpenAI model

Browse Combinatorics Graph theoryLean-checked results