Random triangle removal
About this app
Random triangles vanish from the complete graph one after another until none is left. The deleted triangles flash, the triangle-free leave glows. A series up to n = 2000 shows that the leave divided by n^1.5 tends to 1/(2√2) ≈ 0.354. openai/math family 188 (formalised in Lean).
What it is about
Start with the complete graph on n vertices, where everyone is connected to everyone, and keep deleting the three edges of a uniformly random remaining triangle until none is left. How many edges remain at the end? Bollobás and Erdős conjectured in 1990 that about n^(3/2) remain. Bohman, Frieze and Lubetzky proved the exponent n^(3/2+o(1)) in 2015, and Joos and Kühn predicted the exact constant. An AI-generated preprint in github.com/openai/math (family 188) claims that the leftover divided by n^(3/2) tends to 1/(2√2) ≈ 0.354. The catalogue lists the main theorem as formalised in Lean; the preprint is not peer-reviewed.
What the app shows
The process runs visibly: deleted triangles flash, and the triangle-free remainder lights up at the end. You can remove a single triangle, run to the end or reshuffle; a panel counts edges, removed and still possible triangles and the ratio leftover / n^1.5. The measurement series runs complete processes in the background up to n = 2000 and plots them against n, with averages and the line 1/(2√2). The runs are exact uniform simulations; they illustrate the constant but do not prove it.
What to look for
For small n the leftover varies a lot from run to run; only the series reveals the constant. As n grows, the spread shrinks and the averages slowly climb towards 0.354. At n = 2000 the average is still just below, around 0.35, because the theorem is about the limit and convergence is slow. The proof tracks the survival of individual edges with a recursive priority test, which the app does not show.
Frequently asked questions
- What is the random triangle removal process?
- In random triangle removal you start with the complete graph and repeatedly delete the three edges of a randomly chosen triangle. Every remaining triangle has the same chance of being picked. The process stops when the graph is triangle-free.
- How many edges are left after random triangle removal?
- Bollobás and Erdős conjectured about n^(3/2) edges, a vanishing fraction of all n(n−1)/2 edges. Bohman, Frieze and Lubetzky proved this order of magnitude up to factors n^(o(1)) in 2015. The exact constant 1/(2√2) comes from the prediction of Joos and Kühn.
- Has the constant 1/(2√2) in triangle removal been proved?
- An AI-generated preprint in the catalogue github.com/openai/math (family 188) claims that the leftover divided by n^(3/2) tends to 1/(2√2) ≈ 0.354, in mean square and hence in probability. The catalogue lists the main theorem as formalised in Lean. The preprint has not yet been peer-reviewed.
- What can I try out in this app?
- You set the number of vertices n and watch triangles vanish one at a time or in a full run. A counter shows the remaining edges and the ratio leftover / n^1.5. A series of runs up to n = 2000 shows the values approaching the constant 0.354.
Subject: Open problems, solved by AI
More from Open problems, solved by AI
- Anderson localisation: 2D vs. 3D (3D)
- Barker sequences and circulant Hadamard matrices
- Barnette's conjecture: a round trip over every polyhedron (3D)
- Birkhoff billiards: only the ellipse has no gaps
- Cardy's formula — percolation in a random tiling
- The plane is not five-colourable (Hadwiger–Nelson)
- Double-dimer loops and CLE₄
- Triangular billiards — irrational angles mix (3D)
A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps