---

Claim. Write $r_k(K_3;K_m)$ for the least $N$ such that every $(k+1)$-coloring of the edges of $K_N$ contains a monochromatic triangle in one of the first $k$ colors or a monochromatic $K_m$ in the last. Alon and Rödl prove (Theorem 3.2 of the library's source card) that for every fixed $k\ge1$

$$r_k(K_3;K_m)=\tilde\Theta(m^{k+1}),$$

that is, $m^{k+1}$ up to polylogarithmic factors, with the bounds inside the proof made explicit: $r_k(K_3;K_m)\ge\Omega(m^{k+1}/(\log m)^{2k+\delta})$ for every $\delta>0$ and large $m$, and $r_k(K_3;K_m)\le c_km^{k+1}(\log\log m)^{k-1}/(\log m)^k$; for $k=1$ the value is the Ajtai--Komlós--Szemerédi and Kim result $r(K_3,K_m)=\Theta(m^2/\log m)$, cited in the proof. In the notation of Problem 553, $R(3,3,n)=r_2(K_3;K_n)$ and $R(3,n)=r_1(K_3;K_n)$, so the case $k=2$ against the case $k=1$ gives

$$\frac{R(3,3,n)}{R(3,n)}\ge\Omega\Bigl(\frac{n}{(\log n)^{3+\delta}}\Bigr)\to\infty,$$

which is the statement. The paper states the problem as its Conjecture 1.1, attributed to Erdős and Sós, and says it is solved "in a strong form"; the problem asks only that the ratio be unbounded, not for its rate. The lower bound comes from random shifts of blow-ups of explicit triangle-free pseudorandom graphs, with large independent sets counted through eigenvalues.

Dating. No preprint of the paper is recorded; the page is dated by the issue month the Crossref record gives (volume 25, issue 2, March 2005), and the day in the page name is a placeholder.

Depends on. Ajtai, Komlós and Szemerédi 1980, Theorem 3 and Kim 1995, Theorem 1.1, the upper and lower bounds of the case $k=1$, which the proof cites; the rest is the paper's own theorem.

Acceptance. Reviewed: the site's curator, T. F. Bloom, labels the problem PROVED and credits the solution to this paper in the page's commentary. Refereed: Combinatorica 25 (2005), no. 2, 125--141 (the Crossref record). Locators are pages of the authors' final manuscript, which has not been compared with the journal typesetting. He and Wigderson's 2020 paper on multicolor Ramsey numbers presents its bounds as generalizing this theorem, a further attestation. The titles of the eighty citing records Semantic Scholar listed on 2026-09-17 show no dispute or sharper determination of $R(3,3,n)$. Formalization: Erdos553.lean in Boris Alexeev's repository of formalized Erdős problems, added on 2026-08-17 and linked above at a pinned commit, declares itself a formalization of a solution, names Alon and Rödl as informal authors and Codex and GPT-5.6 Sol as formal authors; its theorem erdos_553 derives the divergence of $R(3,3,m)/R(3,m)$ from $R(3,3,m)\gg m^3/(\log m)^6$ and $R(3,m)\le m^2$. This corpus has not built it, so it gives no formalized evidence.

Read depth. Conjecture 1.1 (p. 2), Theorem 3.2 with the two explicit bounds inside its proof (pp. 6--7) and the Remark after it (p. 7) are checked clause by clause; the proof is followed for structure only; the one-line passage from the two bounds to the divergence of the ratio is an authored check on the problem page that warrants nothing here. Nothing is independently reviewed in this corpus. The exact power of $\log n$ in $R(3,3,n)$ is open in the sources searched and is not this problem's question.