Problem 159

There exists some constant $c>0$ such that

$R(C_4,K_n) \ll n^{2-c}.$

Graph theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

Open, the site's label. No proof, disproof, preprint or proof claim for the exact statement was found in the search whose scope the Current assessment records. The known bounds are

c_1\Bigl(\frac{n}{\log n}\Bigr)^{3/2}<R(C_4,K_n)\le(1+o(1))\Bigl(\frac{n}{\log n}\Bigr)^2,

the lower bound being Spencer's Theorem 3.1 ([Sp77], printed p. 75), and the upper bound [CLRZ00] Corollary 3 (i) at $m=2$ (p. 53), the order $n^2/(\log n)^2$ the site displays; [Er84d] (display (33), p. 67) attributes that order to an observation of Szemerédi from the Ajtai--Komlós--Szemerédi independence lemma without a printed proof, and [CLRZ00] (pp. 51--52) confirms the attribution, says the original proof "was never published, and its details were subsequently forgotten", and prints one. [EFRS78] Theorem 2 is the earlier $c_2(n\log\log n/\log n)^2$ . Neither side saves a fixed power of $n$ . This is a bounded negative finding, not a certificate of openness.

Er78: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978), Congressus Numerantium XXI (1978), 29--40; relation (5), printed p. 34. Library home: Erdős 1978.
EFRS78: Erdős, P., Faudree, R. J., Rousseau, C. C. and Schelp, R. H., On cycle-complete graph Ramsey numbers. J. Graph Theory 2 (1978), no. 1, 53--64, doi:10.1002/jgt.3190020107. Library home: Erdős 1978.
Sp77: Spencer, J., Asymptotic lower bounds for Ramsey functions. Discrete Math. 20 (1977), no. 1, 69--76, doi:10.1016/0012-365X(77)90044-9. Theorem 3.1 and Theorem 3.3, printed p. 75 (PDF p. 7 of the publisher's open-archive file); the bound [EFRS78] quotes as display (1.4) is Theorem 3.3. Library home: Spencer 1977; paged at Spencer 1977, Theorem 3.1 and Spencer 1977, Theorem 3.3.
BoKe10: Bohman, T. and Keevash, P., The early evolution of the $H$ -free process. Invent. Math. 181 (2010), no. 2, 291--336, doi:10.1007/s00222-010-0247-x; arXiv:0908.0429v1 (4 August 2009, the only arXiv version). Theorem 1.3. Library home: Bohman and Keevash 2010 (the card cites the arXiv version).
CLRZ00: Caro, Y., Li, Y., Rousseau, C. C. and Zhang, Y., Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers. Discrete Math. 220 (2000), no. 1--3, 51--56, doi:10.1016/S0012-365X(99)00399-4. Corollary 3 (i), printed p. 53 (PDF p. 3 of the publisher's open-archive file), and the remark on Szemerédi's bound, pp. 51--52. Library home: Caro 2000.
MuVe19: Mubayi, D. and Verstraëte, J., A note on pseudorandom Ramsey graphs. arXiv:1909.01461v2 (29 September 2019). Cited from the arXiv abstract; the citation record lists a journal version, not compared.
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), 25--42. Site source key; Part V, display (2), "Prove that $r(K(n),C(4))<n^{2-\varepsilon}$ "; the journal page of the passage is not recorded. Library home: Erdős 1981.
Er84d: Erdős, P., Extremal problems in number theory, combinatorics and geometry. Proceedings of the International Congress of Mathematicians (Warsaw, 1983), Vol. 1 (1984), 51--70. Site source key; displays (31)--(33) on printed pp. 66--67: the conjecture $r(K(m),C_4)<m^{2-\varepsilon}$ , the unproved $r(K(m),C_4)/r(K(m),C_3)\to0$ and "Szemerédi recently observed that $r(K(m),C_4)<cm^2/(\log m)^2$ ", derived from the Ajtai--Komlós--Szemerédi independence lemma; no proof is printed. Library home: Erdős 1984.

Problem 159

Status

Proof claims

Discussion