Problem 720

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 such that in any $2$ -colouring of the edges of $H$ there is a monochromatic copy of $G$ .

Is it true that, if $P_n$ is the path of length $n$ , then

\hat{R}(P_n)/n\to \infty

and

\hat{R}(P_n)/n^2 \to 0?

Is it true that, if $C_n$ is the cycle with $n$ edges, then

\hat{R}(C_n) =o(n^2)?

Source: erdosproblems.com/720

Graph theory
Ramsey theory

Wiki page

Status

SolvedAnswered

An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.

The site labels the problem PROVED, a label that attaches to the resolution of the problem: the answers are no to (i) and yes to (ii) and (iii), because both size Ramsey numbers are linear. Paths: Beck [Be83b] proved $\hat r(P_n)<900n$ for large $n$ ; the paper is not held, and the bound is quoted from the introduction of the refereed paper [JKOP19] (p. 2), from Beck's own 1990 sequel [Be90] (p. 34) and from Erdős's report of 1982 [Er82e] (p. 70); [DrPe22] (p. 1) attests only that Beck's bound is linear, without the constant. Cycles: the first published proof of $\hat r(C_n)=O(n)$ in the sources read is Corollary 11 (Haxell, Kohayakawa and Łuczak 1995) of [HKL95] (Combin. Probab. Comput. 4 (1995), refereed), which gives the induced and multicolor bound $r_e^{\mathrm{ind}}(C^\ell,r)\le c_r\ell$ ; that paper's preprint attributes the plain linear bound to Bollobás, Burr and an unnamed third person, named Reimer in the published abstract, as a personal communication of November 1992, while [Er82e] credits Beck with $\hat r(C_n,C_n)<C_2n$ as an unpublished result in 1982, which is the site's attribution. The site's label PROVED belongs to this resolution and is recorded here; the first question's answer is no. The frontmatter standing derives from the claim pages Beck 1983 (the path bound, covering (i) and (ii); the site also credits the paper with the cycle bound, which the sources read do not attest, so the page does not claim it) and Haxell, Kohayakawa and Łuczak 1995 (the induced bound for cycles, with the induced paths it gives, answering all three questions), which record the results, their postings and their acceptance evidence. The frontmatter lists the three questions as the problem's parts. Haxell, Kohayakawa and Łuczak's accepted full claim answers all three, and Beck's accepted partial claim answers (i) and (ii), so the derived standing is solved. The derived claim is answered, because the answers are no to (i) and yes to (ii) and (iii). Erdős offered a prize for a proof or disproof of the pair (i)--(ii) in [Er81], p. 9 of the re-typeset copy, after offering separate prizes for each and for an asymptotic formula in [Er78], p. 33.

EFRS78b: Erdős, P., Faudree, R. J., Rousseau, C. C. and Schelp, R. H., The size Ramsey number. Period. Math. Hungar. 9 (1978), no. 1--2, 145--161, doi:10.1007/BF02018930 (received 16 March 1976). The definitions, p. 146; the path passage, p. 161. Library home: Erdős et al. 1978; the passage is recorded on its Section 8 page.
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 (Crossref record accessed). Not held here; quoted second-hand as stated.
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 introduction (pp. 34--36) and the end of Section 5 (pp. 44--45) are the basis here, the attestation on its Beck 1990, Remark (p. 34) page and Theorem 3 on its Beck 1990, Theorem 3 page. Its display (1) attests $\hat r(P_n)<900n$ "(see Beck 1983 ...)", its Theorems 1--2 concern trees, and its Theorem 3 gives $\hat r(P_n)>(9/4-\epsilon)n$ ; those pages say nothing about cycles.
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 (Crossref record accessed). Theorem 10 and Corollary 11, preprint p. 11; the attribution, p. 3 and reference [6], p. 21. Library home: Haxell, Kohayakawa and Łuczak 1995 (the authors' preprint, without 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 (Crossref record accessed); arXiv:1701.07348v1 (25 January 2017). Theorem 1.1 and the introduction, p. 2. Library home: Javadi et al. 2019.
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. The attestation, p. 1. Library home: Draganić and Petrova 2022.
Er76c: Erdős, P., Some recent problems and results in graph theory, combinatorics and number theory. Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1976), 3--14, as the formal-conjectures statement file for this problem cites it; the site cites p. 5. Not held.
Er78: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Proc. Ninth Southeastern Conf. (Boca Raton, 1978), Congr. Numer. XXI (1978), 29--40; Section 4, printed p. 33. Library home: Erdős 1978.
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), no. 1, 25--42; Part V, display (4), on p. 9 of the re-typeset copy, which has its own pagination. Library home: Erdős 1981.
Er81c: Erdős, P., Some new problems and results in graph theory and other branches of combinatorial mathematics. Combinatorics and graph theory (Calcutta, 1980), Lecture Notes in Math. 885 (1981), 9--17; display (17), printed p. 14. Not a source key of this problem on the site; it restates (i) and (ii). Library home: Erdős 1981.
Er82e: Erdős, P., Some of my favourite problems which recently have been solved. Proc. Int. Math. Conf. (Singapore, 1981), North-Holland Math. Stud. 74 (1982), 59--79; Section 3, printed p. 70 and the first line of p. 71. Library home: Erdős 1982.
DuPr15: Dudek, A. and Prałat, P., An alternative proof of the linearity of the size-Ramsey number of paths. Combin. Probab. Comput. 24 (2015), 551--555; arXiv:1405.1663 ( $\hat r(P_n)<137n$ ). Not held; abstract accessed. Their later bound $\hat r(P_n)\le74n$ for sufficiently large $n$ is quoted from [JKOP19], p. 2.
BaDe19: Bal, D. and DeBiasio, L., New lower bounds on the size-Ramsey number of a path. arXiv:1909.06354 (Electron. J. Combin., per the citation index). Not held; abstract accessed: every graph with at most $(3.75-o(1))n$ edges has a two-coloring with no monochromatic path of order $n$ .

Problem 720

Status

Proof claims

Discussion