Exact solutions to the Erdős-Rothschild problem

Let k := (k1,...,k2) 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 kc. Write F (n; k) to denote the maximum of F (G;k) over all graphs G on n vertices. There are currently very few known exact (or asymptotic) results for this problem, posed by Erdős and Rothschild in 1974. We prove some new exact results for n → ∞: (i) A sufficient condition on k which guarantees that every extremal graph is a complete multipartite graph, which systematically recovers all existing exact results. (ii) Addressing the original question of Erdős and Rothschild, in the case k = (3,..., 3) of length 7, the unique extremal graph is the complete balanced 8-partite graph, with colourings coming from Hadamard matrices of order 8. (iii) In the case k = (k+ 1, k), for which the sufficient condition in (i) does not hold, for 3 ≤ k ≤ 10, the unique extremal graph is complete k-partite with one part of size less than k and the other parts as equal in size as possible