paper

The Erdős-Rothschild problem on edge-colourings with forbidden monochromatic cliques

arXiv:1605.05074 · doi:10.1017/S0305004116001031

Abstract

Let be a sequence of natural numbers. For a graph , let denote the number of colourings of the edges of with colours such that, for every , the edges of colour contain no clique of order . Write to denote the maximum of over all graphs on vertices. This problem was first considered by Erdős and Rothschild in 1974, but it has been solved only for a very small number of non-trivial cases. We prove that, for every and , there is a complete multipartite graph on vertices with . Also, for every we construct a finite optimisation problem whose maximum is equal to the limit of as tends to infinity. Our final result is a stability theorem for complete multipartite graphs , describing the asymptotic structure of such with in terms of solutions to the optimisation problem.

arXiv comment16 pages, to appear in Math. Proc. Cambridge Phil. Soc

Cited by in corpus (1)