Problem 553

Let $R(3,3,n)$ denote the smallest integer $m$ such that if we $3$ -colour the edges of $K_m$ then there is either a monochromatic triangle in one of the first two colours or a monochromatic $K_n$ in the third colour. Define $R(3,n)$ similarly but with two colours. Show that

\frac{R(3,3,n)}{R(3,n)}\to \infty

as $n\to \infty$ .

Source: erdosproblems.com/553

Graph theory
Ramsey theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. The status-defining source is Theorem 3.2 of Alon and Rödl, Combinatorica 25 (2005), 125--141 (refereed): $r_k(K_3;K_m)=\tilde\Theta(m^{k+1})$ for every fixed $k\ge1$ , that is, $m^{k+1}$ up to polylogarithmic factors. Its case $k=2$ against its case $k=1$ (which is the Ajtai--Komlós--Szemerédi and Kim value $r(K_3,K_m)=\Theta(m^2/\log m)$ , cited in the proof) gives $R(3,3,n)/R(3,n)\ge\Omega(n/(\log n)^{3+\delta})$ for every $\delta>0$ , so the ratio tends to infinity; the paper states Conjecture 1.1 in the problem's words and says it is solved "in a strong form". The site's commentary records the same resolution. The claim page Alon and Rödl 2005 records the theorem, its publication and the acceptance evidence (the curator's credit and the refereed venue); the frontmatter standing is derived from it.

AlRo05: Alon, N. and Rödl, V., Sharp bounds for some multicolor Ramsey numbers. Combinatorica 25 (2005), no. 2, 125--141, doi:10.1007/s00493-005-0011-9. Pages and statement numbers are those of the authors' "Final Version" manuscript (15 pages) on Alon's publication list: Conjecture 1.1, p. 2; Theorem 3.2, p. 6. Library home: Alon and Rödl 2005.
ErSo80: Erdős, P. and Sós, V. T., Problems and results on Ramsey--Turán type theorems. Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Arcata, 1979), Congressus Numerantium XXVI (1980), 17--23. The site's source and [AlRo05]'s reference [15]; not held.
Sh83: Shearer, J. B., A note on the independence number of triangle-free graphs. Discrete Math. 46 (1983), no. 1, 83--87, doi:10.1016/0012-365X(83)90273-X. The site's source for $R(3,n)\ll n^2/\log n$ : Theorem 1, printed p. 83, the independence bound $\alpha\ge n(d\ln d-d+1)/(d-1)^2$ for triangle-free graphs of average degree $d$ , from which $R(3,n)\le(1+o(1))n^2/\log n$ follows by the elementary step recorded on its result page. Library home: Shearer 1983; paged at Shearer 1983, Theorem 1. It is not the Shearer paper [AlRo05]'s proof uses, which is [Sh95].
Sh95: Shearer, J. B., On the independence number of sparse graphs. Random Structures Algorithms 7 (1995), no. 3, 269--271, doi:10.1002/rsa.3240070305. The independence bound in the proof of Theorem 3.2 ([AlRo05]'s reference [22]): Corollary 1, printed p. 271, $\alpha\ge c(r)\,n\ln d/(d\ln\ln d)$ for $K_r$ -free graphs ( $r\ge4$ ) on $n$ vertices with maximum degree $d$ and large $d$ , the constant not explicit. Library home: Shearer 1995; paged at Shearer 1995, Corollary 1.
AKS80: Ajtai, M., Komlós, J. and Szemerédi, E., A note on Ramsey numbers. J. Combin. Theory Ser. A 29 (1980), no. 3, 354--360, DOI 10.1016/0097-3165(80)90030-8. The upper bound $r(K_3,K_m)=O(m^2/\log m)$ , [AlRo05]'s reference [2]: Theorem 3, printed p. 358, $R(3,x)<100x^2/\ln x$ , from Theorem 2, printed p. 355. Library home: Ajtai and Szemerédi 1980; paged at Ajtai and Szemerédi 1980, Theorem 2 and Ajtai and Szemerédi 1980, Theorem 3.
Ki95: Kim, J. H., The Ramsey number $R(3,t)$ has order of magnitude $t^2/\log t$ . Random Structures Algorithms 7 (1995), 173--207. The matching lower bound, [AlRo05]'s reference [17]. Library home: Kim 1995; paged at Kim 1995, Theorem 1.1.
HeWi20: He, X. and Wigderson, Y., Multicolor Ramsey numbers via pseudorandom graphs. Electron. J. Combin. 27 (2020); arXiv:1910.06287 (v3 8 February 2020). Cited for its abstract; recorded below.

Problem 553

Status

Proof claims

Discussion