Problem 559

Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges that is Ramsey for $G$ .

If $G$ has $n$ vertices and maximum degree $d$ then prove that

\hat{R}(G)\ll_d n.

Source: erdosproblems.com/559

Graph theory
Ramsey theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved, in the site's label (DISPROVED; page last edited 18 January 2026, accessed 2026-09-17). The statement fails for $d=3$ : Tikhomirov's Theorem 1.1 [Ti22b] gives, for every $n\ge1$ , an $n$ -vertex graph of maximum degree at most three with $\hat r(G')\ge cn\exp(c\sqrt{\log n})$ , which is not $O(n)$ ; the arXiv version is the one accepted by Combinatorica, where the paper appeared in 2024 (refereed; the journal text was not compared). The original disproof is Theorem 1 of [RoSz00] (p. 258): positive constants $c$ and $\alpha$ and a graph $G$ with $|V|=n$ and maximum degree $3$ such that $\hat r(G)\ge cn(\log_2n)^\alpha$ , proved for $n\ge n_0$ with $c=\frac1{10}$ and $\alpha=\frac1{60}$ . The statement holds for paths [Be83b], bounded-degree trees [FrPi87] and graphs of maximum degree two (cycles by [HKL95] and [JKOP19]; all such graphs through bounded treewidth, second-hand), so the failure begins at $d=3$ . How large $\hat r$ can be for cubic graphs is open: between $n\exp(c\sqrt{\log n})$ and $n^{3/2+o(1)}$ [DrPe22]. The claim pages Rödl and Szemerédi 2000 and Tikhomirov 2022 record the two refereed disproofs with their postings and acceptance evidence; the frontmatter standing derives from these pages. The positive cases have partial claim pages: Beck 1983 (paths), Friedman and Pippenger 1987 (bounded-degree trees), Haxell, Kohayakawa and Łuczak 1995 (cycles) and Javadi, Khoeini, Omidi and Pokrovskiy 2017 (cycles, explicit constants). The bounded-treewidth result [KLWY21] has no claim page, since its statement is known here only through [DrPe22].

Be83b: Beck, J., On size Ramsey number of paths, trees, and circuits. I. J. Graph Theory 7 (1983), no. 1, 115--129, doi:10.1002/jgt.3190070115. Not held. The site cites it for the question and for the path case; its bound $\hat R(P_n)<900n$ is quoted here from [JKOP19], p. 2.
Be90: Beck, J., On size Ramsey number of paths, trees and circuits. II. Mathematics of Ramsey theory, Algorithms Combin. 5, Springer, Berlin (1990), 34--45. Library home: Beck 1990; its p. 36 Problem, recorded on the Beck 1990, Problem (p. 36) page, asks to "Decide whether $\hat r(G_{n,D})<c_2(D)\cdot n$ " for graphs $G_{n,D}$ of $n$ edges and maximal degree $D$ , the problem's question with edges in place of vertices; cited for the question by [Ti22b] (its reference [1]) and [CNT22] (its reference [5]).
RoSz00: Rödl, V. and Szemerédi, E., On size Ramsey numbers of graphs with bounded degree. Combinatorica 20 (2000), no. 2, 257--262, doi:10.1007/s004930070024 (received 21 December 1998, per p. 257). Beck's Problem, Theorem 1 and the constants fixed in its proof, p. 258; the Fact, p. 259; the Concluding Remark's conjecture, p. 261. Library home: Rödl and Szemerédi 2000; Theorem 1 on the Rödl and Szemerédi 2000, Theorem 1 page.
FrPi87: Friedman, J. and Pippenger, N., Expanding graphs contain all small trees. Combinatorica 7 (1987), no. 1, 71--76, doi:10.1007/BF02579202. Not held; its tree result is quoted from [DrPe22], p. 2.
KRSS11: Kohayakawa, Y., Rödl, V., Schacht, M. and Szemerédi, E., Sparse partition universal graphs for graphs of bounded degree. Adv. Math. 226 (2011), no. 6, 5041--5065, doi:10.1016/j.aim.2011.01.004. Not held; its bound is quoted from [Ti22b] p. 1 and [DrPe22] p. 2.
HKL95: Haxell, P. E., Kohayakawa, Y. and Łuczak, T., The induced size-Ramsey number of cycles. Combin. Probab. Comput. 4 (1995), no. 3, 217--239, doi:10.1017/S0963548300001619. Theorem 10 and Corollary 11 (preprint p. 11). Library home: Haxell, Kohayakawa and Łuczak 1995 (the locators are to the authors' preprint, which has no journal pagination).
JKOP19: Javadi, R., Khoeini, F., Omidi, G. R. and Pokrovskiy, A., On the size-Ramsey number of cycles. Combin. Probab. Comput. 28 (2019), no. 6, 871--880, doi:10.1017/S0963548319000221; arXiv:1701.07348v1 (25 January 2017). Theorem 1.1, p. 2; Theorems 3.4 and 3.6, pp. 11--12. Library home: Javadi et al. 2019.
CNT22: Conlon, D., Nenadov, R. and Trujić, M., The size-Ramsey number of cubic graphs. Bull. Lond. Math. Soc. 54 (2022), no. 6, 2135--2150, doi:10.1112/blms.12682; arXiv:2110.01897v2 (23 April 2023). Theorems 1.1 and 1.2, p. 2. Library home: Conlon, Nenadov and Trujić 2022.
DrPe22: Draganić, N. and Petrova, K., Size-Ramsey numbers of graphs with maximum degree three. arXiv:2207.05048v2 (19 September 2025); J. London Math. Soc. (2) 111 (2025), no. 3, e70116, doi:10.1112/jlms.70116 (not compared). Theorem 1.1, p. 2. Library home: Draganić and Petrova 2022.
Ti22b: Tikhomirov, K., On bounded degree graphs with large size-Ramsey numbers. arXiv:2210.05818v2 (22 July 2023, "revised version, accepted in Combinatorica"); Combinatorica 44 (2024), no. 1, 9--14, doi:10.1007/s00493-023-00056-1 (published online 21 August 2023; not compared). Theorem 1.1, p. 1. Library home: Tikhomirov 2022.
KLWY21: Kamčev, N., Liebenau, A., Wood, D. R. and Yepremyan, L., The size Ramsey number of graphs with bounded treewidth. SIAM J. Discrete Math. 35 (2021), no. 1, 281--293. Not held; cited by [DrPe22] (its reference [26]) for the maximum-degree-two case.

Problem 559

Status

Proof claims

Discussion