Skip to content

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?

\[ \mathbb Ef(n)\asymp n^{3/2}\quad\text{and}\quad f(n)=O(n^{3/2})\text{ with high probability?} \]

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.

Back to catalogue · Compendium introduction