Problem 166

Prove that

R(4,k) \gg \frac{k^3}{(\log k)^{O(1)}}.

Source: erdosproblems.com/166

Graph theory
Ramsey theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved, the site's label (PROVED). Mattheus and Verstraete's Theorem 1 (Annals of Mathematics (2) 199 (2024), 919--941; refereed, received June 2023, accepted October 2023) states $r(4,t)=\Omega(t^3/\log^4t)$ as $t\to\infty$ , so the statement holds with the fourth power of the logarithm. The page numbers cited are those of the arXiv version marked as the updated journal version; the printed text has not been compared with it. The upper bound $R(4,k)\ll k^3/(\log k)^2$ is Theorem 6 of Ajtai, Komlós and Szemerédi (1980, refereed: $R(k,x)\le(5000)^kx^{k-1}/(\ln x)^{k-2}$ for every fixed $k$ and large $x$ , at $k=4$ ); its constant $1+o(1)$ is Li, Rousseau and Zang's 2001 concluding remark (for any fixed $k$ , $r(k,n)\le(1+o(1))n^{k-1}/(\log n)^{k-2}$ as $n\to\infty$ , the case $l=1$ of their Theorem 2, at $k=4$ ). The earlier lower bound of exponent $5/2$ is Spencer's Theorem 2.2 (1977, refereed: $R(k,t)\ge c(t/\ln t)^\beta[1-o(1)]$ for fixed $k\ge3$ with $\beta=[\binom k2-1]/(k-2)$ , which is $5/2$ at $k=4$ ), improved to $\Omega(t^{5/2}/\log^2t)$ by the $K_4$ -free process, quoted second-hand from [MaVe23], which credits Bohman and Keevash 2010; their paper itself (arXiv v1, pp. 2 and 33) credits that bound to Bohman's 2009 paper The triangle-free process (Adv. Math. 221) and states its own Theorem 1.2 only for $s\ge5$ . The claim page Mattheus and Verstraete 2023 records the theorem, its postings and its acceptance evidence, and the frontmatter standing derives from it.

MaVe23: Mattheus, S. and Verstraete, J., The asymptotics of $r(4,t)$ . Ann. of Math. (2) 199 (2024), no. 2, 919--941, DOI 10.4007/annals.2024.199.2.8 (received 19 June 2023, revised 17 October 2023, accepted 18 October 2023, published online 5 March 2024, per the journal's article page); arXiv:2306.04007 (v1 6 June 2023; v5 20 February 2024, "Updated journal version", 24 pages). Theorem 1, p. 3; displays (1)--(2), p. 2. Library home: Mattheus and Verstraete 2023.
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. Theorem 6, printed p. 359, with its proof on pp. 359--360, checked for structure only. Library home: Ajtai and Szemerédi 1980; paged at Ajtai and Szemerédi 1980, Theorem 6.
LRZ01: Li, Y., Rousseau, C. C. and Zang, W., Asymptotic upper bounds for Ramsey functions. Graphs Combin. 17 (2001), 123--128, DOI 10.1007/s003730170060 (received 11 May 1998, final version 24 March 1999). Theorem 2, printed p. 124, and the concluding remark $r(k,n)\le(1+o(1))n^{k-1}/(\log n)^{k-2}$ for fixed $k$ , printed p. 127. Library home: Li, Rousseau and Zang 2001; paged at Li, Rousseau and Zang 2001, Theorem 2.
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 2.2, printed p. 74. Library home: Spencer 1977; paged at Spencer 1977, Theorem 2.2.
BoKe10: Bohman, T. and Keevash, P., The early evolution of the $H$ -free process. Invent. Math. 181 (2010), 291--336; credited by [MaVe23] pp. 2--3 with the previous best lower bound for $r(4,t)$ , which this paper itself (arXiv v1, pp. 2 and 33) credits to T. Bohman, The triangle-free process, Adv. Math. 221 (2009), no. 5, 1653--1677, DOI 10.1016/j.aim.2009.02.018. Library home: Theorem 1.2 (Bohman and Keevash 2010) (its statement for fixed $s\ge5$ is paged there).
Er81c: Erdős, P., Some new problems and results in graph theory and other branches of combinatorial mathematics. Lecture Notes in Math. 885 (1981), 9--17; items (6) and (6'), printed p. 11. Not a site key for this problem. Library home: Erdős 1981.
Er90b: Erdős, P., Problems and results on graphs and hypergraphs: similarities and differences. Mathematics of Ramsey theory, Algorithms Combin. 5, Springer (1990), 12--28; display (14) and the prize offer, printed p. 18. Library home: Erdős 1990.
Er91: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, 1988), Wiley (1991), 397--406. Not held.
Er93: Erdős, P., Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350; Chapter II, the $r(4,n)>n^{3-\epsilon}$ expectation and Spencer's $cn^{5/2}$ , printed p. 339. The site cites p. 339. Library home: Erdős 1993.
Er97c: Erdős, P., Some of my favorite problems and results. The mathematics of Paul Erdős, I, Algorithms Combin. 13, Springer (1997), 47--67; the retracted expectation $r_2(4,n)>n^{3-\epsilon}$ and Spencer's $cn^{5/2}$ , printed pp. 62--63. Library home: Erdős 1997; paged at Erdős 1997, Problem (pp. 62–63).
Va99: Various, Some of Paul's favorite problems. Booklet for the conference "Paul Erdős and his mathematics", Budapest (1999); the site cites item 3.51, "Prove $r(4,n)>n^{3-\varepsilon}$ ". Library home: Various 1999.
Mo26: Morris, R., Some recent results in Ramsey theory. Proc. ICM 2026, Vol. 2, 210--239, DOI 10.1137/25m1833369 (published online 13 July 2026); arXiv:2601.05221 (v1 8 January 2026, 37 pages). Theorem 1.3 and display (3), p. 3. Expert attestation, not a review. Library home: Morris 2026.

Problem 166

Status

Proof claims

Discussion