The sharp terminal leave in random triangle removal

1 · The essentials

Imagine a set of points with a connection between every pair. Pick three points whose three connections are still present, choosing at random with every available triangle equally likely. Erase those three connections and repeat until no triangle remains. The question is how many connections are left when this process stops. The main result says that, as the number $n$ of points grows, the number left divided by $n^{3/2}$ approaches $1/ (22)$ . This describes both the average outcome and the increasingly small chance of a substantial departure from that value after division. The main result has a Lean formalization, although the supplied material does not specify its exact coverage.

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

As an imperfect image, imagine a board of pegs with a string joining every pair of pegs: each turn, you randomly select an intact three-string triangle and cut its strings. Eventually no intact triangle remains, even though some strings are still on the board; those leftover strings are what the result counts.

Why it matters

The result identifies the precise leading constant for the number of edges left by this random deletion process, rather than only its scale. The manuscript presents it as resolving the triangle case of the sharp-constant conjecture of Joos and Kühn. Its convergence statement also controls both the normalized expectation and the probability of deviations.

2 · Going further

Start with the complete graph on $n$ vertices. At each step, choose uniformly among the triangles currently present and remove all three of the chosen triangle’s edges. Let $M_{n}$ be the number of edges remaining when no triangle is available. The precise result is $M_{n} / n^{3/2} \to 1/ (22)$ in $L^{2}$ as $n \to \infty$ .

Here, $L^{2}$ convergence means that $E [(M_{n} / n^{3/2} - 1/ (22))^{2}] \to 0$ . Thus the statement controls the expected squared error of the normalized count, not merely its average. The abstract also states convergence in probability and convergence of the normalized expectation to the same constant.

The manuscript places this result in the context of the Joos–Kühn sharp-constant conjecture and identifies it as the triangle case. The supplied abstract states the conclusion but does not describe the argument, so no proof strategy can be extracted from this source. Only the main manuscript is supplied; no relationship to companion manuscripts is described.

Useful notions

Graphs, vertices, and edges
Complete graphs and triangles
Uniform random choice
Expectation and squared error
Convergence of random quantities

What was known before / what is new

Before

The source identifies a sharp-constant conjecture of Joos and Kühn as the context for this result. It supplies no earlier bounds, partial results, or account of the conjecture’s history.

New

The main result identifies the terminal edge count as asymptotic to $n^{3/2} / (22)$ , with mean-square convergence after normalization by $n^{3/2}$ . The manuscript presents this as resolving the triangle case of the Joos–Kühn conjecture. The abstract also states the corresponding limits in probability and for the normalized expectation.

Limits and assumptions

The statement concerns a complete starting graph and a process that chooses uniformly among the remaining triangles and deletes all three edges at each step. It is an asymptotic statement as $n$ grows, not an exact edge count for a fixed $n$ ; the supplied abstract gives no quantitative error bound or rate of convergence. The main result has a Lean formalization, but the supplied material does not detail its scope or establish separate formal coverage of every stated consequence. Only the triangle case is addressed here, and the source does not specify the status of other cases or further open questions.

Mini glossary

Complete graph: A graph in which every pair of distinct vertices is joined by an edge.
Triangle: Three vertices with all three edges between them present.
Terminal edge count: The number of edges left when the process stops because no triangle remains.
Normalized count: Here, the terminal edge count divided by $n^{3/2}$ .
Mean-square convergence: Convergence in which the expected squared difference from the limiting value tends to zero, also called $L^{2}$ convergence.
Convergence in probability: Convergence in which the probability of differing from the limit by more than any fixed positive amount tends to zero.

Keywords : Random triangle removal · Terminal edge count · Mean-square convergence

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)

Starting from the complete graph on n vertices, repeatedly delete a uniformly chosen remaining triangle. The terminal edge count is asymptotic to $n^{3/2} / (22)$ , with mean-square convergence after normalization by n^3/2. This proves the triangle case of the Joos–Kühn sharp-constant conjecture.

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/188.md

Manuscripts in this family

★

The sharp terminal leave in random triangle removal

25/09/2026

To be verified

Starting from the complete graph on n vertices, repeatedly remove the three edges of a uniformly chosen remaining triangle. We prove that the number of edges left at termination, divided by n^3/2, converges in L² to $1/ (22)$ . This proves the triangle case of the sharp-constant conjecture of Joos and Kühn. In particular, the same limit holds in probability and for the normalized expectation.

PDF GitHub folder