The random triangle-removal process: does the surviving edge count $f(n)$ scale as $n^{3/2}$? (Erdős #1155)
Statement
Build a random graph as follows: start with the complete graph $K_n$; at each step choose a triangle uniformly at random among all triangles currently present in the graph and delete its three edges; repeat until the graph is triangle-free. Let $f(n)$ be the (random) number of edges remaining when the process stops. Describe the typical structure and parameters of the resulting graph. In particular, is it true that $\mathbb{E}f(n)\asymp n^{3/2}$ and that $f(n)\ll n^{3/2}$ almost surely? (Here $\asymp$ means bounded above and below by absolute constant multiples, and $\ll$ means bounded above by a constant multiple.)
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable in Lean/Coq preferred, otherwise a full written proof with all steps) establishing both $\mathbb{E}f(n)\asymp n^{3/2}$ and $f(n)\ll n^{3/2}$ almost surely, together with a description of the typical structure of the terminal graph. ADVANCES (each independently checkable): (a) rigorously improve the almost-sure upper bound below the best exponent stated in the background — currently $n^{3/2+o(1)}$ — e.g. to $n^{3/2}(\log n)^{O(1)}$, with proof; (b) prove a matching rigorous lower bound $f(n)\gg n^{3/2}$; or (c) a reproducible high-precision simulation study that estimates the scaling exponent and structural statistics with stated confidence intervals over large $n$, with the simulation code and raw data (an empirical data advance, not a resolution). NEVER require human judgement or human-authored artifacts. Deliver the proof file, or the code plus the measured exponent with error bars.
Background
Posed by Bollobás and Erdős, who asked it at the 'Quo Vadis, Graph Theory?' conference in Fairbanks, Alaska in 1990; it is recorded in [Bo98, p.231] and [Va99, 3.61] as motivated by the task of generating a random triangle-free graph. Listed as open on erdosproblems.com/1155 (fetched 2026-07-13, status 'open', tagged 'graph theory'). Frontier: Grable [Gr97] proved that for every $\epsilon>0$, $\mathbb{P}(f(n)>n^{7/4+\epsilon})\to 0$, giving a first sub-$n^{7/4}$ ceiling. Bohman, Frieze, and Lubetzky [BFL15] then determined the exponent up to lower-order terms, proving $f(n)=n^{3/2+o(1)}$ almost surely — i.e. for every $\epsilon>0$, $\mathbb{P}(n^{3/2-\epsilon}<f(n)<n^{3/2+\epsilon})\to 1$ — via the differential-equation / self-correcting martingale method used for random triangle-free process analyses. What remains open is the sharper conjecture that removes the $o(1)$ in the exponent: that $\mathbb{E}f(n)\asymp n^{3/2}$ with true polynomial order and $f(n)\ll n^{3/2}$ almost surely, together with a finer description of the limiting structure (degree distribution, independence number). No Erdős prize is attached. Attacker's tool: large-scale Monte-Carlo simulation of the removal process to estimate the exponent and empirical structural statistics, combined with differential-equation-method and martingale-concentration analysis to sharpen the almost-sure upper bound past $n^{3/2+o(1)}$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1155 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.