The Number of Edge Colorings with no Monochromatic Cliques

Let F(n,r,k) denote the maximum possible number of distinct edge‐colorings of a simple graph on n vertices with r colors which contain no monochromatic copy of K k . It is shown that for every fixed k and all n>n 0 (k), F ( n , 2 , k ) = 2 t k − 1 ( n )and F ( n , 3 , k ) = 3 t k − 1 ( n ), where t k−1 (n) is the maximum possible number of edges of a graph on n vertices with no K k (determined by Turán's theorem). The case r=2 settles an old conjecture of Erdős and Rothschild, which was also independently raised later by Yuster. On the other hand, for every fixed r>3 and k>2, the function F(n,r,k) is exponentially bigger thanr t k − 1 ( n ). The proofs are based on Szemerédi's regularity lemma together with some additional tools in extremal graph theory, and provide one of the rare examples of a precise result proved by applying this lemma.