Skip to content

Erdős Problem #720

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (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.

The question in plain language

Define the size Ramsey number Rhat(G) as the smallest number of edges of a host graph H such that every red–blue edge-colouring of H has a monochromatic copy of G. Erdős–Faudree–Rousseau–Schelp asked three different asymptotic questions: (i) does Rhat(P_n)/n→∞ for a path of length n? (ii) does Rhat(P_n)/n²→0? (iii) does Rhat(C_n)=o(n²)? Beck (1983) proved the path bound Rhat(P_n)=O(n). For cycles, a separate 1995 result of Haxell, Kohayakawa and Łuczak gives Rhat(C_n)=O(n); their induced size-Ramsey theorem is stronger than the ordinary two-color cycle assertion. Thus both linear estimates hold, but they must not be attributed jointly to Beck. Thus (i) is DISPROVED, (ii) and (iii) PROVED. The maintained page's single aggregate badge 'PROVED' must not be read as an affirmative resolution of all three.

A small example

Any host arrowing a path P_n must contain at least one copy of P_n, hence at least n edges (the path is specified to have length n). Thus Rhat(P_n)≥n. Beck's linear upper bound gives Rhat(P_n)=Θ(n), so Rhat(P_n)/n stays bounded above AND bounded away from zero; it does not diverge, while the ratio divided by n² tends to zero. Similarly, a cycle with n edges requires Rhat(C_n)≥n and the independently sourced Haxell–Kohayakawa–Łuczak upper bound gives Θ(n).

What is known

The maintained #720 attributes the questions to Erdős, Faudree, Rousseau and Schelp [EFRS78b] and broadly credits Beck [Be83b]. The publisher abstract for Beck, On size Ramsey number of paths, trees, and circuits. I, Journal of Graph Theory 7 (1983), 115–129 explicitly proves linearity for paths, and does not claim the cycle theorem. The publisher abstract for Haxell, Kohayakawa and Łuczak, The induced size-Ramsey number of cycles, Combinatorics, Probability and Computing 4 (1995), 217–239 proves linearity for the induced cycle size-Ramsey number, which implies the ordinary cycle linear bound; it cites earlier cycle-related work by Bollobás and Burr and collaborators. These are correctly attributed published results; the full proofs and earliest historical priority for ordinary cycles have not been independently replayed here. Be careful about P_n denoting n vertices versus n edges: the catalogue explicitly uses path LENGTH n, whereas many original papers index vertices; either convention yields equivalent Θ(n) asymptotics but different finite values. Source page reports PROVED because its overall questions were resolved, though one answer was negative.

GCL's current state

The authenticated original issue source return preserves the individual theorem status and source assumptions. This authenticated source return is neither a new theorem nor a GCL mathematical certificate. The manuscript is publicly available after protected merge; separate exact-hash V2 editorial acceptance is controlled by the admissions ledger.

What remains

ERDOS-720-MIXED_ANSWER_STATUSES. Check Beck (1983) for paths separately from Haxell–Kohayakawa–Łuczak (1995) for cycles; verify the earliest ordinary-cycle priority and the EFRS78b wording, plus exact edge/vertex path indexing and constants. Prove the trivial n-edge host lower bound and derive the three distinct yes/no asymptotic answers from the source-locked upper bound. Acceptance: a three-row status table with no false affirmative claim for (i).

Sources and claim boundaries

Maintained Erdős Problem #720; Beck 1983 paths primary publisher; Haxell–Kohayakawa–Łuczak 1995 cycle publisher; authenticated issue audit. Full original proof text and branch-protected formal dependencies not independently replayed. The source draft has been protected-merged and verified with live public MathJax. Independent theorem proof verification and any separate V2 editorial admission are not implied by that deployment.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1991 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • 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