Improved Bound On The Maximum Number Of Clique-Free Colorings With Two And Three Colors

Given integers r,k ≥ 2 let κr,k +1(G) denote the number of distinct edge colorings of G with r colors, which are Kk +1-free, i.e., which contain no monochromatic clique on k + 1 vertices. Alon et al. [J. Lond. Math. Soc. (2), 70 (2004), pp. 273–288] show that for r ∈ {2, 3} and all k ≥ 2 the maximum of κr,k +1(G) over all G on n vertices is achieved only by the Turán graph, provided n > n0(k) is sufficiently large. The proof uses Szemerédi’s regularity lemma and yields an n0(k) which is tower type with height exponential in k. As a lower bound the authors observed that n0(k) must be at least exponential in k. In this paper we essentially close the gap between the upper and the lower bound for n0(k). Answering the question posed by Alon et al. we show that the lower bound is of correct order and that it suffices to choose n0(k) = exp(Ck4) for some absolute constant C.