Search

The sharp terminal leave in random triangle removal

Randomly erasing triangles from a complete graph leaves about n^(3/2)/(2√2) edges at the end.

1 paper September 25, 2026 Explained by AI

Join every pair of n dots, then keep erasing a random triangle until none is left. It was known that about n^(3/2) edges survive, up to smaller factors. This paper proves the exact leading constant: the leftover is about n^(3/2)/(2√2). This settles the triangle case of a conjecture by Joos and Kühn.

First step
—
Significance
Major
It pins down the exact constant in a much-studied random process, settling a 2025 conjecture.
Trust
Formal proof listed
Field
Combinatorics
1 paper

The explanation

Take four dots and join every pair. That gives six lines, called edges, and four triangles. Pick one triangle and erase its three edges. The three edges left all meet at the fourth dot. They form no triangle, so the game stops with 3 edges left.

Now do the same with n dots, all pairs joined. This is the complete graph on n vertices. At each step, choose one remaining triangle uniformly at random and erase its edges. Stop when no triangle is left. The edges that survive are called the leave. How many are there?

For 1,000 dots there are 499,500 edges to start. Most get erased. The paper's answer predicts about 11,180 left, roughly 2.2%. That figure comes from the formula n^(3/2)/(2√2), where 1/(2√2) is about 0.354. The formula describes the trend as n grows, not an exact count for any one n.

The size of the leave was a long-standing question. Bollobás and Erdős conjectured in 1990 that it grows like n^(3/2). Spencer, and separately Rödl and Thoma, showed it is a vanishing share of all edges. Bohman, Frieze and Lubetzky pinned down the power 3/2, up to smaller factors. The leading constant stayed open. In 2025, Joos and Kühn conjectured a constant, which for triangles is 1/(2√2).

This paper proves that constant. Divide the leave by n^(3/2). As n grows, the result settles at 1/(2√2) in a strong sense: its average squared error shrinks to zero. This is called convergence in L². It implies the typical value and the average value both approach the same constant.

The difficulty is the end of the process. Early on, the graph looks evenly random, and earlier tools track it well. The paper uses Joos and Kühn's results for that early stretch, and nothing else from outside. Near the end, few triangles remain, and each edge's fate depends on its neighbours. Rough estimates are not enough to get the constant. The paper redraws the remaining process with fresh random priorities on the triangles. It then compares each edge's chance of surviving with a simple formula from Spencer's earlier work. The hard part is showing these chances hold together for pairs of edges, not just single ones.

The result is about starting from all pairs joined. It does not give a constant for other starting graphs, or for removing larger shapes. It also does not describe how much the leave varies around its typical size.

How sure is this? A computer proof checker called Lean has checked a formal version of the main theorem. The Lean scope note says it covers the convergence in L² to 1/(2√2), in probability, and for the average. No specialist review of the paper has been published.

What it doesn't show. This does not give the constant for other starting graphs or larger shapes, or describe the spread around the typical size.

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 main convergence statement; no specialist review is published, and the result covers only the complete-graph start.

Words used

Complete graph
A set of dots with every pair joined by an edge.
Triangle removal process
Repeatedly erase the three edges of a randomly chosen remaining triangle until none is left.
Leave
The edges still present when no triangle remains.
Convergence in L²
The average squared distance from the target value shrinks to zero.
With high probability
With chance tending to one as the number of dots grows.

The original paper

Lean notes

All quoted lines (10)
  1. At each step, choose uniformly from the triangles whose three edges are still present, and delete those edges.
    The sharp terminal leave in random triangle removal Back to text
  2. Bollob\'as and Erd\Hos conjectured in 1990 that the expected leave has order n3/2n^{3/2}, as reported in.
    The sharp terminal leave in random triangle removal Back to text
  3. Spencer's branching-process analysis and the independent nibble argument of R\"odl and Thoma showed that the leave is o(n2)o(n^2) with high probability.
    The sharp terminal leave in random triangle removal Back to text
  4. Bohman, Frieze and Lubetzky gave a short proof of the bound O(n7/4log⁡5/4n)O(n^{7/4}\log^{5/4}n) and subsequently proved Fn=n3/2+o(1)F_n=n^{3/2+o(1)} with high probability.
    The sharp terminal leave in random triangle removal Back to text
  5. Their Conjecture 16.2 predicts an asymptotic constant for the terminal leave; its triangle specialization is 1/(22)1/(2\sqrt2) in probability.
    The sharp terminal leave in random triangle removal Back to text
  6. The following theorem proves this triangle case with L2L^2 convergence.
    The sharp terminal leave in random triangle removal Back to text
  7. The only external proof input is the early-prefix control from Joos and K\"uhn, specialized in Section ….
    The sharp terminal leave in random triangle removal Back to text
  8. Give the triangles of this graph fresh independent uniform priorities and scan them in increasing order, accepting a triangle when all its edges remain.
    The sharp terminal leave in random triangle removal Back to text
  9. This is Spencer's scalar branching law after the time change c=Dtc=Dt.
    The sharp terminal leave in random triangle removal Back to text
  10. The theorem concerns removal from KnK_n; it does not assert a sharp constant for arbitrary starting graphs or for general hypergraph removal, or a fluctuation law.
    The sharp terminal leave in random triangle removal Back to text

Other sources

  1. openai/math, Lean scope note for family 188 (2026) The formalization proves that the number of edges at termination, divided by n3/2n^{3/2}, converges in L2L^2 to 1/(22)1/(2\sqrt2).
  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