The Erdos-Rothschild problem on edge-colourings with forbidden monochromatic cliques

© Copyright 2017 Cambridge Philosophical Society. Let k = (k 1 , ⋯, k s ) be a sequence of natural numbers. For a graph G, let F(G; k) denote the number of colourings of the edges of G with colours 1, ⋯, s such that, for every c ∈ {1, ⋯, s}, the edges of colour c contain no clique of order k c . Write F(n; k) to denote the maximum of F(G; k) over all graphs G on n vertices. This problem was first considered by Erd.os and Rothschild in 1974, but it has been solved only for a very small number of non-trivial cases. We prove that, for every k and n, there is a complete multipartite graph G on n vertices with F(G; k) = F(n; k). Also, for every k we construct a finite optimisation problem whose maximum is equal to the limit of log 2 F(n; k)/(n/2) as n tends to infinity. Our final result is a stability theorem for complete multipartite graphs G, describing the asymptotic structure of such G with F(G; k) = F(n; k) · 2 o(n2) in terms of solutions to the optimisation problem.