Problem 1155

Construct a random graph on $n$ vertices in the following way: begin with the complete graph $K_n$ . At each stage, choose uniformly a random triangle in the graph and delete all the edges of this triangle. Repeat until the graph is triangle-free.

Describe the typical parameters and structure of such a graph. In particular, if $f(n)$ is the number of edges remaining, then is it true that

\mathbb{E}f(n)\asymp n^{3/2}

and that $f(n) \ll n^{3/2}$ almost surely?

Source: erdosproblems.com/1155

Graph theory

Wiki page

Status

Open

No claim settles this problem.

Open. What is proved: $f(n)=n^{3/2+o(1)}$ with high probability, that is $\mathbb P(n^{3/2-\epsilon}<f(n)<n^{3/2+\epsilon})\to1$ for every $\epsilon>0$ , by Bohman, Frieze and Lubetzky [BFL15], Theorem 1 (refereed; the theorem and the introduction are recorded on its library card), which settles the exponent conjectured by Bollobás and Erdős but neither of the displayed questions as asked, since both concern the order $n^{3/2}$ itself. One partial claim is accepted: a preprint of the OpenAI mathematics release of 2026-09-25 proves $f(n)/n^{3/2}\to1/(2\sqrt2)$ in $L^2$ , hence in probability and in mean, which answers both displayed questions with the sharp constant; it is recorded on its claim page (OpenAI, 2026) as accepted on its Lean declaration, which the corpus's verification built and audited, though the manuscript has no independent review. It does not address the request for the typical structure, for which no claim is recorded, so the problem stays open. No literature search beyond the sources named on this page was made, so this page certifies no openness.

BFL15: Bohman, Tom and Frieze, Alan and Lubetzky, Eyal, Random triangle removal. Adv. Math. 280 (2015), 379--438; arXiv:1203.4223. Library home: Bohman, Frieze and Lubetzky 2015 (Theorem 1 and the introduction are recorded on the card).
Bo98: Bollobás, Béla, To prove and conjecture: Paul Erdős and his mathematics. Amer. Math. Monthly 105 (1998), 209--237; pp. 231--232 per the site and its thread. Not held.
Gr97: Grable, David A., On random greedy triangle packing. Electron. J. Combin. 4 (1997), Research Paper 11, 19 pp. Not held; its bounds are taken from the site, the introduction of [BFL15] and Section 1 of [OAI26].
Va99: Various, Some of Paul's favorite problems. Booklet produced for the conference "Paul Erdős and his mathematics", Budapest, July 1999; item 3.61 in Section 3.4, Random structures. Library home: Various 1999 (Kovač's public image-only scan of paired pages; the item is on the right leaf of its PDF p. 6).
JoKu24: Joos, Felix and Kühn, Marcus, The hypergraph removal process. arXiv:2412.15039 (version 2). Not held; cited by [OAI26] for the conjectured constant (its Conjecture 16.2) and for the only external proof input of its argument.
OAI26: OpenAI, The sharp terminal leave in random triangle removal. OpenAI Math Release preprint, 25 September 2026, in the release's repository at the revision the claim page pins; a preprint with no journal or arXiv version. Library home: OpenAI 2026; the main result is paged at OpenAI 2026, Theorem 1.1.

Problem 1155

Status

Proof claims

Discussion