The Library
The ErdosRothschild problem on edgecolourings with forbidden monochromatic cliques
Tools
Pikhurko, Oleg, Staden, Katherine and Yilma, Zelealem B. (2017) The ErdosRothschild problem on edgecolourings with forbidden monochromatic cliques. Mathematical Proceedings of the Cambridge Philosophical Society, 163 (2). pp. 341356. doi:10.1017/S0305004116001031

PDF
WRAPErdosRothschildproblemmonochromaticPikhurko2017.pdf  Accepted Version  Requires a PDF viewer. Download (750Kb)  Preview 
Official URL: https://doi.org/10.1017/S0305004116001031
Abstract
Let k := (k1, . . . , ks) 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. This problem was first considered by Erd˝os and Rothschild in 1974, but it has been solved only for a very small number of nontrivial 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 log2 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(n 2 ) in terms of solutions to the optimisation problem.
Item Type:  Journal Article  

Subjects:  Q Science > QA Mathematics  
Divisions:  Faculty of Science, Engineering and Medicine > Science > Mathematics  
Library of Congress Subject Headings (LCSH):  Mathematics., Graph theory., Computer algorithms., Number theory.  
Journal or Publication Title:  Mathematical Proceedings of the Cambridge Philosophical Society  
Publisher:  Cambridge University Press  
ISSN:  03050041  
Official Date:  September 2017  
Dates: 


Volume:  163  
Number:  2  
Page Range:  pp. 341356  
DOI:  10.1017/S0305004116001031  
Status:  Peer Reviewed  
Publication Status:  Published  
Access rights to Published version:  Restricted or Subscription Access  
Funder:  Engineering and Physical Sciences Research Council (EPSRC), European Research Council (ERC)  
Grant number:  306493, EP/K012045/1 
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 
Downloads
Downloads per month over past year