The precise residue of random triangle removal

← All digests

Family 188 · Combinatorics
Importance 3/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

Begin with a complete network on $n$ vertices: every pair is joined by an edge. Choose one of its triangles uniformly at random and erase that triangle’s three edges. Repeat, always choosing uniformly among the triangles still present. Eventually there is no triangle left, so the procedure stops.

How many edges survive? The answer is not zero in general. The final graph can contain many edges without containing a triangle, and the choices made along the way affect which edges become stranded. This is a simple example of a random greedy algorithm: make an available local move, without planning for the final outcome.

Write $F_n$ for the number of surviving edges. Earlier work identified its principal scale as $n^{3/2}$, up to a factor of the form $n^{o(1)}$. The manuscript in this family claims the precise leading constant:

$$F_n\approx \frac{n^{3/2}}{2\sqrt{2}}.$$

It also claims a strong form of concentration around that value. The interesting issue is how the last stages of a dependent process can be described accurately enough to recover a constant, after most of the original edges have already disappeared.

2. Background and essential definitions

Triangles, packings, and the leftover graph

A graph here is finite, undirected, and simple: there are no loops or repeated edges. A triangle consists of three vertices and all three edges between them. The complete graph $K_n$ has $\binom n2=n(n-1)/2$ edges.

Every triangle deleted by the procedure is disjoint in edges from every triangle deleted earlier. Thus the removed triangles form a triangle packing. Thinking of each triangle as a three-element subset of the vertex set, no pair of vertices belongs to more than one chosen triple. This is also called a partial Steiner triple system.

The leave is the graph of unused edges. At termination it is triangle-free, since otherwise another deletion would be possible. Triangle-free does not mean empty: a graph whose vertices split into two groups and whose edges run only between groups has no triangle, even when many edges are present.

If $T_n$ triangles were removed, then

$$3T_n+F_n=\binom n2.$$

Consequently, understanding the leave also describes how close the greedy packing comes to covering all pairs. The claimed leave occupies a vanishing proportion of all edges, but still has order $n^{3/2}$.

What kind of convergence is claimed?

For random variables $X_n$, convergence in probability to $a$ means that the chance of $|X_n-a|>\varepsilon$ tends to zero for every fixed positive $\varepsilon$. Convergence in mean square, also called $L^2$ convergence, means

$$\mathbb E[(X_n-a)^2]\longrightarrow0.$$

Here $\mathbb E$ denotes expectation. Mean-square convergence controls both typical behavior and the contribution of unusually large deviations. It implies convergence in probability and convergence of the expectations.

The notation $o(1)$ means a quantity tending to zero as $n$ grows. A statement holding with high probability has probability tending to one. Neither phrase says that a particular small instance must behave close to the limiting formula.

3. Development history and previous partial results

The manuscript traces the prediction that the expected leave should have order $n^{3/2}$ to Bollobás and Erdős in 1990. The broader setting is the study of random greedy packings, where a very simple rule can create an almost complete combinatorial design.

Spencer’s 1995 branching-process treatment and work of Rödl and Thoma in 1996 established asymptotic packing results: the unused fraction tends to zero. For triangle removal, this corresponds to a leave of size $o(n^2)$. Such a result shows that the procedure is efficient at first order, while leaving the much smaller residue largely undetermined.

Subsequent work progressively reduced bounds on that residue. Grable obtained bounds approaching an exponent of $11/6$, and described a further improvement. Bohman, Frieze, and Lubetzky’s 2010 paper gave an upper bound of order $n^{7/4}(\log n)^{5/4}$. Their later Random triangle removal, published in 2015, established

$$F_n=n^{3/2+o(1)}$$

with high probability. This settled the main exponent, but an $n^{o(1)}$ factor can still drift and therefore does not determine a leading constant.

Joos and Kühn’s 2025 work developed a much broader theory of hypergraph removal processes. Its triangle-removal conjecture specifies the constant $1/(2\sqrt2)$. The present manuscript claims that constant and mean-square convergence, rather than another improvement to the exponent alone.

The source explicitly uses the earlier Joos–Kühn analysis for a sufficiently long initial portion of the process. Its new argument concerns the continuation into the final regime. This distinction matters: the claimed advance builds on existing control of the early evolution instead of replacing the whole history of random greedy analysis.

4. What the new manuscripts claim

The family contains one manuscript, M1. Its main statement is

$$\mathbb E\left[ \left(\frac{F_n}{n^{3/2}}-\frac{1}{2\sqrt2}\right)^2 \right]\longrightarrow0.$$

The randomness is exactly that of successive uniform choices among the currently available triangles, starting from $K_n$.

The stated consequences include

$$\frac{F_n}{n^{3/2}}\xrightarrow{\mathbb P}\frac{1}{2\sqrt2}, \qquad \mathbb E[F_n]=\left(\frac{1}{2\sqrt2}+o(1)\right)n^{3/2}.$$

The arrow denotes convergence in probability. Mean-square convergence also entails that the variance of $F_n$ is $o(n^3)$; variance measures the mean squared distance from a random variable’s expectation.

This is an asymptotic theorem about the terminal number of edges. It does not identify a limiting distribution for the finer fluctuations, an exact finite-size expectation, or a formula for an arbitrary starting graph. Nor does it assert that every maximal triangle packing has this leave. Uniform randomness is part of the statement.

5. Why the advance matters

Importance: 3/5. The claimed result completes a substantial prediction about a central example of a random greedy process. Its significance lies in determining the terminal constant and controlling fluctuations at the main scale, after the exponent was already known.

The distinction between an exponent and a constant is particularly meaningful here. During most of the process, averages and approximate uniformity offer useful descriptions. Near termination, an edge’s fate depends on a web of earlier choices. A sharp answer must retain enough of that dependence to distinguish one constant from another.

The method also explains why a branching-process prediction can survive this complicated finite environment. That is potentially useful intuition for other greedy algorithms, although M1’s theorem remains specific to triangle removal from a complete graph.

For designs, the conclusion quantifies the defect left by an uncomplicated construction procedure. It does not say that the leave is the smallest possible defect, or that a carefully planned packing could not do better.

6. The main idea

Stop early enough to retain a regular environment

The argument first pauses the process at a stage where the remaining graph has edge density $p$, with $p$ slightly larger than $n^{-1/2}$. At that point it has approximately

$$m=\frac{n^2p}{2}$$

edges, and a typical surviving edge belongs to about

$$D=np^2$$

triangles. The letter $m$ in this explanation counts remaining edges. The parameter $D$ measures how many competing deletion opportunities surround one edge.

The cited earlier theory supplies a sufficiently regular graph at this stopping point. The remaining task is to follow the continuation all the way to the end, where straightforward uniform-density approximations become inadequate.

Give possible deletions random priorities

One can represent the continuation by assigning independent uniform priorities between zero and one to the triangles present at the pause. Scan them in priority order and accept a triangle precisely when all three of its edges are still available. The manuscript uses the equivalence of this representation with the required random greedy continuation.

To decide whether a particular edge survives up to priority $t$, inspect earlier triangles containing it. Whether one of those triangles deletes the edge depends on whether its other two edges have survived until that earlier priority. Their survival produces further questions, and so on.

This backward exploration resembles a tree of dependencies. An idealized version gives different appearances of a triangle independent randomness, even when the finite graph would identify them. In the approximately uniform setting, the corresponding survival probability has the scalar form

$$q(t)=\frac{1}{\sqrt{1+2Dt}}.$$

Here $t$ is a priority cutoff, not the number of deleted triangles. The shape of this formula reflects the fact that deletion of one edge needs two other surviving edges.

Recover the constant, then justify the approximation

At the final cutoff $t=1$, the idealized number of survivors is

$$mq(1)=\frac{n^2p}{2\sqrt{1+2np^2}}.$$

Because the chosen stopping point has $D=np^2$ tending to infinity, the leading factors of $p$ cancel:

$$\frac{mq(1)}{n^{3/2}}\longrightarrow\frac{1}{2\sqrt2}.$$

This calculation explains the constant; it is not by itself the finite-process argument. Actual dependency explorations can meet the same edge or triangle more than once. Such collisions create correlations absent from the idealized tree.

M1 describes two ingredients for controlling the discrepancy. First, information about local neighborhoods stabilizes the survival equations despite small irregularities. Second, it counts the patterns that can witness a collision in one or two simultaneous explorations, keeping track of the order of their priorities.

The two-exploration estimate is crucial. One randomly selected edge reveals the expected surviving fraction; two independently selected edges reveal its second moment. The claimed comparison error is smaller than their joint survival probability. This supplies enough precision for the first and second moments to yield mean-square convergence, rather than only a plausible estimate of the mean.

7. Scope, limitations, and open questions

The initial graph and the selection rule are essential. Starting with a different dense graph, choosing triangles with a bias, or deleting another fixed shape gives a different problem. The broader removal-process literature motivates such extensions, but M1 does not state a universal version of its constant.

The terminal graph is triangle-free, yet it is not sampled uniformly from triangle-free graphs. It is also distinct from the usual triangle-free process, which starts with no edges and adds edges while avoiding triangles. Similar vocabulary should not obscure these different probability distributions.

The theorem concerns the total leave, rather than a complete description of its geometry. It does not specify the degree distribution, component structure, or the smaller scale and shape of the remaining fluctuations. Those are natural further questions once the leading constant is fixed.

Finally, the asymptotic result supplies no optimized numerical cutoff beyond which the approximation has a chosen accuracy. Its explanatory achievement is a limiting law for a concrete algorithm, supported in the manuscript by control of the dependent final phase.

8. Sources and further reading

• Bohman, Frieze, and Lubetzky, A note on the random greedy triangle-packing algorithm, for the earlier quantitative upper bound.
• Bohman, Frieze, and Lubetzky, Random triangle removal, for the $n^{3/2+o(1)}$ scale and the process’s development.
• Joos and Kühn, The hypergraph removal process, version 2, for the broader removal framework, the early-stage input, and the sharp-constant conjecture discussed by M1.

M1 supplies the detailed references to the early packing results and the stated terminal analysis.

Source manuscripts

• M1. OpenAI, The sharp terminal leave in random triangle removal (September 25, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.