Skip to content

Erdős Problem #163

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

A graph \(H\) is \(d\) degenerate when every nonempty subgraph of \(H\) has a vertex of degree at most \(d\). Its ordinary Ramsey number \(R(H)\) is the least \(N\) such that every red-blue edge colouring of \(K_N\) contains a monochromatic copy of \(H\).

Burr and Erdős conjectured that for every fixed integer \(d\ge1\), there is a constant \(C_d\) such that every \(d\) degenerate graph on \(n\) vertices satisfies

\[ R(H)\le C_d n. \]

The factor \(C_d\) must depend on \(d\) but not on the number of vertices. Merely having bounded average degree in \(H\) itself is weaker than requiring all subgraphs to have bounded average degree.

A small example

Every forest is 1-degenerate, because each nonempty subforest has a vertex of degree zero or one. The conjecture asserts that forests have Ramsey numbers growing only linearly in their number of vertices. A star can have very high maximum degree and still be 1-degenerate, so replacing degeneracy by a maximum-degree restriction discards important cases.

A cycle is 2-degenerate, and bipartite graphs can be highly degenerate; the statement covers both bipartite and nonbipartite graphs with the same fixed degeneracy parameter.

What is known

PROVED. Choongbum Lee's Ramsey numbers of degenerate graphs, Annals of Mathematics 185 (2017), 791–829, proves a quantitative form of the Burr–Erdős conjecture. For graphs \(H\) of degeneracy \(d\) and chromatic number \(r\), the source theorem gives bounds of the form

\[ R(H)\le 2^{\,d2^{O(r)}}|V(H)| \]

after a size threshold depending on \(d\) and \(r\). Since \(r\le d+1\) for a \(d\) degenerate graph, and finitely many smaller graph orders can be absorbed into a constant, the uniform linear in the number of vertices conclusion follows. A weaker explicit form recorded by the maintained Erdős #163 is \(C_d\le2^{2^{O(d)}}\).

A sharper bound \(C_d=2^{O(d)}\) remains conjectural. Thus resolution of the linear in the number of vertices question does not establish optimal dependence on \(d\).

GCL's current state

The pinned catalogue and maintained page classify #163 PROVED. The source issue is #1432. Lee's Annals primary theorem, the chromatic-number reduction and the dependence on \(d\) were checked. The complete dependent-random-choice proof has not been independently reconstructed or formally certified by GCL.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded successor formalizes the elementary implication from \(d\) degeneracy to \((d+1)\) colourability via repeatedly removing a vertex of degree at most \(d\), and derives the uniform constant \(C_d\) from the published Ramsey theorem. Acceptance: an induction with exact quantifiers, explicit finite-size handling, and no assertion of the conjecturally sharper \(2^{O(d)}\) dependence.

Sources and claim boundaries

No new Ramsey theorem, independent proof certification or editorial admission is claimed.

Catalogue and evidence provenance

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