The Library
The Erdos-Rothschild problem on edge-colourings with forbidden monochromatic cliques
Tools
Tools
Tools
Pikhurko, Oleg, Staden, Katherine and Yilma, Zelealem B. (2017) The Erdos-Rothschild problem on edge-colourings with forbidden monochromatic cliques. Mathematical Proceedings of the Cambridge Philosophical Society, 163 (2). pp. 341-356. doi:10.1017/S0305004116001031 ISSN 0305-0041.
|
PDF
WRAP-Erdos-Rothschild-problem-monochromatic-Pikhurko-2017.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 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 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: | 0305-0041 | ||||||||
| Official Date: | September 2017 | ||||||||
| Dates: |
|
||||||||
| Volume: | 163 | ||||||||
| Number: | 2 | ||||||||
| Page Range: | pp. 341-356 | ||||||||
| DOI: | 10.1017/S0305004116001031 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Date of first compliant deposit: | 30 November 2016 | ||||||||
| Date of first compliant Open Access: | 16 September 2017 | ||||||||
| 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
