---

Claim. Beck proves that $\hat r(P_n)<900n$ for all sufficiently large $n$, where $\hat r(G)$ is the size Ramsey number, the least number of edges of a graph every $2$-coloring of whose edges contains a monochromatic copy of $G$. Whether the path has $n$ edges or $n$ vertices changes nothing in the answers below. The site's commentary credits the same paper with the linear bound $\hat r(C_n)=O(n)$ for cycles, and Erdős, reporting Beck's then unpublished results in 1982, states $\hat r(C_n,C_n)<C_2n$ beside the path bound; that attribution is unverified here, as Read depth. says, and this page claims only the path bound.

Covers. Questions (i) and (ii) of Problem 720: (i) $\hat r(P_n)/n$ does not tend to infinity, since it stays below $900$, so the answer is no; (ii) $\hat r(P_n)/n^2\to0$, so the answer is yes. The claim value is answered because one answer is no and the other yes. Question (iii), whether $\hat r(C_n)=o(n^2)$, is outside this page's scope: the refereed proof of $\hat r(C_n)=O(n)$ is Haxell, Kohayakawa and Łuczak's Corollary 11, whose induced cycles also give the path bound, and which has its own claim page. The original question of Erdős, Faudree, Rousseau and Schelp, whether $\lim\hat r(P_n)/n$ exists, is not decided by a linear upper bound and is not part of the site's problem; the known bounds on the ratio for large $n$ lie between $3.75-o(1)$ and $74$.

Depends on. Nothing in this wiki; the result is the paper's own theorem.

Dating. The page is dated by the issue month of the journal record (J. Graph Theory 7 (1983), no. 1, March 1983, per the Crossref record); the day in the page name is a placeholder.

Acceptance. Reviewed: the site's curator, T. F. Bloom, labels the problem PROVED and credits the answer to this paper in the problem's commentary, with both linear bounds (page last edited 7 March 2026, accessed 2026-09-18); this page adopts the credit for the path bound and not for the cycle bound, for the reasons under Read depth. The community database lists the problem as proved. Refereed: J. Graph Theory 7 (1983), no. 1, 115--129. The path bound is attested by four independent sources: Beck's own 1990 sequel (display (1), p. 34, with the remark that the proof puts the path in the larger color class), the introductions of the refereed papers of Javadi, Khoeini, Omidi and Pokrovskiy (2019, p. 2) and of Draganić and Petrova (2025, p. 1, which attests only that the bound is linear, without the constant), and Erdős's 1982 report ([Er82e], p. 70).

Formalization. Boris Alexeev's repository lean-proofs holds a Lean file for the problem, src/latest/ErdosProblems/Erdos720.lean, linked above at the commit of 15 September 2026. Its header declares it a formalization of a solution to the problem, names Beck as the informal author and names Codex and GPT-5.6 Sol as the formal authors; its theorem erdos_720 states the three answers (the path ratio does not tend to infinity, both quadratic ratios tend to zero) together with its own eventual linear bounds for paths and cycles, so it also covers the cycle bound of question (iii) and attributes it to Beck, whom it names as the only informal author. The file imports a development the repository holds beside it. The formal-conjectures statement file FormalConjectures/ErdosProblems/720.lean (added 21 September 2026) marks its three parts research solved and points its formal_proof annotations at this file. Nothing of this Lean was built or audited in this corpus, so it gives no formalized evidence here and the acceptance above rests on the refereed publication and the curator's credit.

Read depth. The paper is not held, and the basis of this page is the four attestations alone; the cycle bound's presence in this paper, whose title names circuits, is not checked. The four attestations speak of paths only, and Haxell, Kohayakawa and Łuczak (p. 3) attribute the plain linear bound for cycles to a 1992 personal communication of Bollobás, Burr and a third person their preprint leaves unnamed, named Reimer in the published abstract. The attribution of the cycle bound is therefore unsettled in the sources read, which is why this page covers (i) and (ii) only; the answer to (iii) does not depend on it. Reopening condition for the read-depth gap: a copy of J. Graph Theory 7 (1983), 115--129, read at its theorems; if it states the cycle bound, this page's scope widens to all three questions.