Burr–Erdős tree Ramsey conjecture

Status partial medium confidence

The specific conjecture r(T,T) ≤ 2n−2 for all trees T on n vertices appears to remain open. The related general Burr–Erdős conjecture — that r(H,H) is linear in n for any fixed degeneracy d (trees are 1-degenerate) — was proven by Choongbum Lee (2017, Annals of Mathematics), establishing r(T,T) = O(n). However, Lee's theorem gives a constant c_1 that is not claimed to equal 2, so the specific upper bound 2n−2 is not settled by this proof. The bound is known to be tight: stars K_{1,n−1} achieve r(K_{1,n−1}, K_{1,n−1}) = 2n−2.

Cited literature (1)

• partial Ramsey numbers of degenerate graphs (2017)
  Choongbum Lee · Annals of Mathematics, 185(3): 791–829

  Proves the general Burr–Erdős conjecture: for every p-degenerate graph H on n vertices, r(H,H) ≤ c_p n for a constant c_p depending only on p. Since trees are 1-degenerate this gives r(T,T) = O(n), but the specific constant 2 (and bound 2n−2) is not established.

Reviewer notes. Two distinct conjectures share the Burr–Erdős name: (1) the general conjecture that r(H,H) = O_d(n) for d-degenerate H, proven by Lee (2017); (2) the specific tree bound r(T,T) ≤ 2n−2, which is item 39 here. Lee's theorem resolves (1) but not (2) as the constant in his proof exceeds 2. The corpus record erdosproblems:547 tracks the same specific statement. Web search was unavailable during this review; the Lee (2017) citation is confirmed indirectly via the verified Wikipedia page on the Burr–Erdős conjecture, not by direct WebFetch of the paper itself. The bound 2n−2 is sharp: stars achieve equality. Partial results for specific tree families (paths, stars, caterpillars, bounded-degree trees) were proven before 2008 and are thus pre-book.

Auto-reviewed 2026-09-10 with claude-sonnet-4-6 (web search enabled).