Problem 163

For any $d\geq 1$ if $H$ is a graph such that every subgraph contains a vertex of degree at most $d$ then $R(H)\ll_d n$ .

Source: erdosproblems.com/163

Graph theory
Ramsey theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. The status-defining source is Theorem 1.1 of Lee, Ramsey numbers of degenerate graphs, Ann. of Math. (2) 185 (2017), 791--829 (refereed; cited from the arXiv v2 of 1 December 2016): there is an absolute constant $c$ such that for all $d$ , $r$ and $n\ge2^{d^22^{cr}}$ , in every two-coloring of a complete graph on at least $2^{d2^{cr}}n$ vertices one color contains every $d$ -degenerate $r$ -colorable graph on at most $n$ vertices, so every $d$ -degenerate $H$ of chromatic number $r$ with $|V(H)|\ge2^{d^22^{cr}}$ has $R(H)\le2^{d2^{cr}}|V(H)|$ . The paper's remark after the theorem settles the conjecture "since all $d$ -degenerate graphs have chromatic number at most $d+1$ " (p. 3); the one-line bridge to the site's wording is written in the Current assessment and named there as authored. The site credits Lee with the solution; the constant is not settled (the site records the conjecture $R(H)\le2^{O(d)}n$ ). The claim page Lee 2015 records the result, its postings and the acceptance evidence.

Le17: Lee, Choongbum, Ramsey numbers of degenerate graphs. Ann. of Math. (2) 185 (2017), no. 3, 791--829, doi:10.4007/annals.2017.185.3.2 (Crossref record read: issue dated 1 May 2017); arXiv:1505.04773 (v2, 1 December 2016, the version cited; 35 pages; the arXiv listing carries no journal reference). Theorem 1.1 and the remarks after it, p. 3; Theorem 1.3 and the hypercube remark, p. 4; Section 7, p. 32. Library home: Lee 2017.
BuEr75: Burr, S. A. and Erdős, P., On the magnitude of generalized Ramsey numbers for graphs. Infinite and finite sets (Colloq., Keszthely, 1973), Vol. I, Colloq. Math. Soc. János Bolyai 10, North-Holland (1975), 215--240. The site's text prints no venue. The Definition and Conjecture, p. 216; $\sigma(G)$ and Lemma 3.3, p. 220; Section 7, pp. 238--239. Library home: Burr and Erdős 1975 (the Rényi archive scan).
Er82e: Erdős, Paul, Some of my favourite problems which recently have been solved. Proceedings of the International Mathematical Conference, Singapore 1981, North-Holland Math. Stud. 74 (1982), 59--79. Display (1), p. 78. Library home: Erdős 1982 (a scan).

Problem 163

Status

Proof claims

Discussion