---

Claim. Let $r_k(K_3;K_m)$ be the least $N$ such that every $(k+1)$-coloring of the edges of $K_N$ has a monochromatic triangle in one of the first $k$ colors or a monochromatic $K_m$ in the last. Theorem 3.2 of Alon and Rödl states that for every fixed $k\ge1$, $r_k(K_3;K_m)=\tilde\Theta(m^{k+1})$, and the lower bound inside its proof is $r_k(K_3;K_m)\ge\Omega(m^{k+1}/(\log m)^{2k+\delta})$ for every $\delta>0$ and all large $m$. The construction (p. 7 of the authors' final manuscript): for $n=2^{3f}$ with $3\nmid f$, Alon's explicit triangle-free $(n,d,\lambda)$-graph is blown up by a factor $r=n^{k/3-2/3}(\log n)^{2-\delta}$ to a triangle-free graph $G$ on $N=nr$ vertices with so few independent sets of size $m=c(k)\,n^{1/3}(\log n)^2$ that $k$ random shifts of $G$ give a $(k+1)$-coloring of $K_N$ with no monochromatic triangle in the first $k$ colors and no $K_m$ in color $k+1$. The theorem is paged at Theorem 3.2 of the library's source card.

What it settles. The paper never states Problem 925; its Conjecture 1.1 concerns the ratio $R(3,3,m)/R(3,m)$ of Problem 553. The conversion is elementary and is written on the problem page: at $k=2$, the graph $H$ formed by the edges of the first two colors has $N=n(\log n)^{2-\delta}$ vertices, its edges are $2$-colored with no monochromatic triangle, so $H$ is not Ramsey for $K_3$, and its independent sets are cliques of the third color, so $\alpha(H)<c\,n^{1/3}(\log n)^2\le c\,N^{1/3}(\log N)^2$. For every $\delta'>0$ this is below $N^{1/3+\delta'}$ once $N$ is large, so along the infinite sequence of these $N$ no independent set of size $N^{1/3+\delta'}$ exists, and the problem's question, which asks for one in every such graph for all large $n$, has answer no for every $\delta>0$. In the site's reformulation, the lower bound $R(3,3,m)\ge\Omega(m^3/(\log m)^{4+\delta})$ refutes $R(3,3,m)\ll m^{3-c}$ for every $c>0$; the site records the same resolution through that reformulation.

Depends on. Nothing in this wiki; the result rests on the cited paper alone, and the elementary conversion above is restated on the problem page.

Acceptance. Refereed: N. Alon and V. Rödl, Sharp bounds for some multicolor Ramsey numbers, Combinatorica 25 (2005), no. 2, 125--141 (the Crossref record, places the article in the March 2005 issue, which this page is named by; the day is a placeholder). Reviewed: the site's curator, T. F. Bloom, records the problem as disproved by Alon and Rödl in the problem's commentary, with the two-sided bound on $R(3,3,m)$ and Sudakov's removal of the $\log\log m$ factor from the upper bound (page labeled DISPROVED). Semantic Scholar's 80 citing records, scanned by title, include no dispute or retraction.

Read depth. The pages cited are those of the authors' final manuscript on the first author's publication list, not compared with the journal typesetting. Theorem 3.2, its two bounds, the construction's parameters inside its proof and the Remark (pp. 6--7) are checked as claims and the proof is read for structure only; the construction's inputs, Alon's explicit graphs and the paper's Theorem 2.1, rest on the paper's citations, and the elementary conversion above is the only argument checked in this corpus.