Skip to content

Erdős Problem #1182

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, ramsey 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 #1182 asks the following. The maintained status is OPEN — FINAL SUBQUESTION DISPROVED.

Let \(R(K_3,G)\) be the ordinary two-edge-color Ramsey number, red triangle versus blue copy of \(G\). Define \(f(n)\) as the maximum edge count among connected \(n\)‑vertex graphs \(G\) satisfying \(R(K_3,G)=2n-1\). Define \(F(n)\) as the largest edge threshold such that every connected \(n\)‑vertex graph with at most \(F(n)\) edges satisfies this equality. Distinguish existential maximum \(f(n)\) from the worst-case threshold \(F(n)\), so trivially \(F(n)\le f(n)\) under relevant existence conventions. In particular, the question asks if \(F(n)/n\to\infty\), which is already answered NO by a linear bound.

A small example

For \(n=3\), the three-vertex path \(P_3\) has \(R(K_3,P_3)=5=2n-1\). Exhaustive enumeration of all \(2^6\) red/blue edge colorings of \(K_4\) finds one with neither red triangle nor blue two-edge path; all \(2^{10}\) colorings of \(K_5\) have one of those structures. This verifies the small tree case, not any asymptotic estimate of \(f(n)\) or \(F(n)\).

What is known

https://www.erdosproblems.com/1182 remains OPEN for determining the best orders and constants of \(f(n),F(n)\), attributed to Burr–Erdős–Faudree–Rousseau–Schelp [BEFRS80]. Chvátal gives \(R(K_3,T_n)=2n-1\) for trees. BEFRS80 established \((17n+1)/15\le F(n)\le(27/4+o(1))n(\log n)^2\) and \(n^{3/2}(\log n)^{1/2}\ll f(n)\ll n^{5/3}(\log n)^{2/3}\), with context for \(n\ge4\). Brandt [Br96] proves \(F(n)\le84n\), decisively refuting the final superlinear-ratio speculation. Do not claim the entire graph extremal problem is solved.

GCL's current state

Authenticated original-issue RESULT/1 research return. GCL independently replayed only the exact bounded fixture in ci/erdos_compendium_007_phase21_checks.py. The general theorem statements above are attributed to their external sources rather than independently certified. This is a locally authored and unaccepted draft.

What remains

Primary-source Brandt 1996 and BEFRS80, verify the graph classes, whether \(n\) is sufficiently large, and strict vs weak inequality in \(F(n)\). Publish a separate verdict 'superlinear \(F(n)/n\) speculation disproved' while retaining open sharp \(F,f\) growth. Reproduce low‑\(n\) graph extremal values independently.

Protected V2 admission requires source fidelity, manuscript QA and any mandatory independent critic reviews; none is inferred from this finite example.

Sources and claim boundaries

https://www.erdosproblems.com/1182 ; [Er78,p.33],[BEFRS80],[Br96], Chvátal tree Ramsey theorem.

Finite evidence receipt: governance/erdos_compendium/batches/EC-BULK-007_FINITE_CHECKS_PHASE21.json. Original GitHub source issue identities unchanged; source-fidelity adjudication, public deployment and V2 editorial acceptance PENDING.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2453 — 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