Problem 78

Let $R(k)$ be the Ramsey number for $K_k$ , the minimal $n$ such that every $2$ -colouring of the edges of $K_n$ contains a monochromatic copy of $K_k$ .

Give a constructive proof that $R(k)>C^k$ for some constant $C>1$ .

Source: erdosproblems.com/78

Graph theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

Open. The nonconstructive bound $R(k)>2^{k/2}$ is Erdős's of 1947. The strongest explicit construction recorded here is Li's Corollary 1.9 (arXiv v2, 30 May 2023; FOCS 2023): a strongly explicit graph on $N$ vertices with no clique or independent set of size $(\log N)^c$ for an unspecified constant $c>1$ , which inverts to the constructive bound $R(k)>2^{k^{1/c}}$ , subexponential in $k$ ; Cohen's earlier $2^{(\log\log n)^{O(1)}}$ (2015; STOC 2016) and the classical constructions listed in his Table 1 are weaker. No explicit construction reaching $O(\log n)$ , and no proof that none exists, was found in the search whose scope the Current assessment records. This is a bounded negative finding, not a certificate of openness. Erdős offered a prize for a constructive proof in 1981, 1988, 1993, 1995 and 1997.

Er69b: Erdős, P., Problems and results in chromatic graph theory. Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), Academic Press (1969), 27--35; display (15) on p. 30 and the request on p. 31. Library home: Erdős 1969.
Er81c: Erdős, P., Some new problems and results in graph theory and other branches of combinatorial mathematics. Combinatorics and graph theory (Calcutta, 1980), Lecture Notes in Math. 885 (1981), 9--17; the offer on p. 12. Library home: Erdős 1981.
Er88: Erdős, P., Problems and results in combinatorial analysis and graph theory. Discrete Math. 72 (1988), 81--92; p. 83. Library home: Erdős 1988.
Er95: Erdős, P., Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas 2 (1995), 165--186; Section II.9 on p. 11 of the author typescript (its running-head number, not the journal's pagination). Library home: Erdős 1995.
Va99: Some of Paul's favorite problems, booklet for the conference "Paul Erdős and his mathematics", Budapest, July 1999; item 3.49. Library home: Various 1999.
Co15: Cohen, G., Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs. Electronic Colloquium on Computational Complexity (2015); arXiv:1506.04428v1 (14 June 2015, the version cited); STOC 2016, 278--284, DOI 10.1145/2897518.2897530; SIAM J. Comput. 50 (2021), no. 3, STOC16-30--STOC16-67, DOI 10.1137/16M1096219. Theorem 1.2 and Table 1, pp. 1--2. Library home: Cohen 2015.
Li23b: Li, X., Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More. arXiv:2303.06802 (v1 13 March 2023; v2 30 May 2023, the version cited); FOCS 2023, 1271--1281, DOI 10.1109/FOCS57990.2023.00075. Corollary 1.9, p. 6; Corollary 7.7, p. 35. Library home: Li 2023.
Er47: Erdős, P., the 1947 note with the probabilistic bound $R(k)>2^{k/2}$ , cited as [Erd47] by [Co15] and as the paper's reference [3] by [Er69b]; not held, and its bibliographic data were not checked here.
Er71: Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press (1971), 97--109. A site key; its library card (card) locates its passage for this problem at its item for this problem (the request on p. 99 for a nontrivial lower bound for $f(n,n)$ by non-probabilistic methods).
Er93: Erdős, P., Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350; Chapter II, display (3) and the prize offer for a constructive proof, printed p. 337 (the displays as the library card gives them). The site cites p. 337. 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 constructive offer after display (4.2), printed p. 62. Library home: Erdős 1997; paged at Erdős 1997, Display (4.2). - Not held: Frankl's 1977 construction (quoted from [Er81c] and [Er88]); Barak, Rao, Shaltiel and Wigderson (Ann. of Math. 2012) and the other entries of Cohen's Table 1; Chattopadhyay and Zuckerman (2016), the two-source extractor for polylogarithmic entropy that [Li23b] cites as its [26].

Problem 78

Status

Proof claims

Discussion