Problem 924

Let $k\geq 2$ and $l\geq 3$ . Is there a graph $G$ which contains no $K_{l+1}$ such that every $k$ -colouring of the edges of $G$ contains a monochromatic copy of $K_l$ ?

Source: erdosproblems.com/924

Graph theory
Ramsey theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

The site labels the problem PROVED. For $k=2$ and every $l$ this is Folkman's Theorem 1 [Fo70] ( $f(k_1,k_2)=\max(k_1,k_2)$ ; SIAM J. Appl. Math. 18 (1970), no. 1, 19--24, refereed). For every $k$ it is the theorem of Nešetřil and Rödl [NeRo76] (J. Combin. Theory Ser. B 20 (1976), no. 3, 243--249, refereed) that for every finite graph $G$ and every number $c$ of colors there is a graph $H$ with $H\to(G)_c$ and clique number $\omega(H)=\omega(G)$ ; with $G=K_l$ and $c=k$ this is the statement. That paper is not held and its theorem is quoted second-hand from the introduction of Spencer's refereed 1975 paper, from Erdős's 1975 report and from the site, which accepts it. Folkman's own paper states the case of more than two colors as a conjecture his methods do not seem to reach. The general case therefore rests on second-hand statements of the Nešetřil--Rödl theorem. The claim pages Folkman 1970 (the case $k=2$ , partial) and Nešetřil and Rödl 1976 (every $k$ ) record the two theorems with their postings and acceptance evidence, and the frontmatter standing derives from them.

Fo70: Folkman, J., Graphs with monochromatic complete subgraphs in every edge coloring. SIAM J. Appl. Math. 18 (1970), no. 1, 19--24, doi:10.1137/0118004. Definitions p. 19, Theorems 1 and 2 p. 20, Remarks pp. 23--24. Library home: Folkman 1970.
NeRo76: Nešetřil, J. and Rödl, V., The Ramsey property for graphs with forbidden complete subgraphs. J. Combinatorial Theory Ser. B 20 (1976), no. 3, 243--249, doi:10.1016/0095-8956(76)90015-0 (the publisher's record dates the issue June 1976). Not held. Quoted second-hand from [Sp75], [Er75b] and the site.
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; printed p. 33. Library home: Erdős 1969.
Er75b: Erdős, P., Problems and results in combinatorial number theory. Journées Arithmétiques de Bordeaux (Conf., Univ. Bordeaux, Bordeaux, 1974), Astérisque 24--25 (1975), 295--310; Chapter IV, printed p. 306. Library home: Erdős 1975.
Sp75: Spencer, J., Restricted Ramsey configurations. J. Combinatorial Theory Ser. A 19 (1975), no. 3, 278--286; the introduction's account of Folkman's and Nešetřil--Rödl's theorems, printed p. 278, and its reference 6, p. 286. Library home: Spencer 1975.
ErHa67: Erdős, P. and Hajnal, A., Research problem 2-5. J. Combinatorial Theory 2 (1967), p. 104. Folkman's reference [1]; the site's key for Problem 582. Not held.
Gr68: Graham, R. L., On edgewise 2-colored graphs with monochromatic triangles and containing no complete hexagon. J. Combinatorial Theory 4 (1968), p. 300. Folkman's reference [2], solving the special case stated in [ErHa67]. Not held.

Problem 924

Status

Proof claims

Discussion