Erdős Problem #1155
Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
UNACCEPTED DRAFT — mathematical editorial review pending
This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.
Review the underlying draft on GitHub.
The question in plain language
Erdős Problem #1155. Delete a uniformly random triangle, including its three edges, over and over until no triangle remains. How many edges typically survive?
Begin K_n. At each step choose uniformly among triangles PRESENT in the current graph, DELETE their three edges and stop when no triangles remain. f(n)=number surviving edges is a random variable. Ask whether E f(n) is Theta(n^{3/2}) AND terminal edge count is O(n^{3/2}) with high probability/asymptotic almost surely. The n^{3/2+o(1)} whp statement is strictly weaker; expectation cannot automatically be derived from a typical exponent without tail control.
A small example
Exact rational-state dynamic programming enumerating all triangle deletions yields expected terminal edges K3=0, K4=3, K5=4. In K4 deletion of any triangle leaves star K1,3. These finite expectations do not imply an asymptotic for growing n.
What is known
https://www.erdosproblems.com/1155 OPEN, Bollobás–Erdős 1990 reported [Bo98,p.231], Vardi [Va99,3.61]. Grable 1997 gave P(f(n)>n^{7/4+epsilon})→0. Bohman–Frieze–Lubetzky [BFL15] proved f(n)=n^{3/2+o(1)} with high probability. This proves exponent but not exact O(n^{3/2}) nor E f(n)∼constant n^{3/2}; no stronger claim certified.
GCL's current state
Authenticated original-issue source return establishes the bounded question, relevant external results, and independently tested finite fixture. The reproducible checks are in ci/erdos_compendium_007_phase18_checks.py.
The source return disposition is PARTIAL. Neither an original-paper proof review nor any Lean kernel replay or protected editorial acceptance has been completed.
What remains
ERDOS-1155-TRIANGLE-REMOVAL-001: source review BFL15 stopping time and high-probability exponent, derive finite Markov transition identities and n≤6 exact expectations, determine if uniform integrability is proved anywhere to justify expectation scale. Avoid substitution of triangle-free process run backwards.
Original sharp expectation/O bound OPEN; BFL proof and rare-tail estimates not independently reviewed.
Sources and claim boundaries
https://www.erdosproblems.com/1155 ; [Bo98],[Gr97],[BFL15]; exact finite recursion only.
This is a locally validated, UNACCEPTED editorial draft. Assertions beyond the exact finite checks are attributed to original external sources and remain subject to source-fidelity review.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2426 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.