The Library
Stability for the Erdős-Rothschild problem
Tools
Pikhurko, Oleg and Staden, Katherine (2023) Stability for the Erdős-Rothschild problem. Forum of Mathematics, Sigma, 11 . e23. doi:10.1017/fms.2023.12 ISSN 2050-5094 .
|
PDF
stability-for-the-erdos-rothschild-problem.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (923Kb) | Preview |
Official URL: http://doi.org/10.1017/fms.2023.12
Abstract
Given a sequence k:=(k1,…,ks) of natural numbers and 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ős and Rothschild in 1974, but it has been solved only for a very small number of nontrivial cases. In previous work with Pikhurko and Yilma, (Math. Proc. Cambridge Phil. Soc. 163 (2017), 341–356), we constructed a finite optimisation problem whose maximum is equal to the limit of log2F(n;k)/(n2) as n tends to infinity and proved a stability theorem for complete multipartite graphs G.
In this paper, we provide a sufficient condition on k which guarantees a general stability theorem for any graph G, describing the asymptotic structure of G on n vertices with F(G;k)=F(n;k)⋅2o(n2) in terms of solutions to the optimisation problem. We apply our theorem to systematically recover existing stability results as well as all cases with s=2 . The proof uses a version of symmetrisation on edge-coloured weighted multigraphs.
Item Type: | Journal Article | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||||||
Library of Congress Subject Headings (LCSH): | Graph theory, Graph coloring, Combinatorial analysis | ||||||||||||
Journal or Publication Title: | Forum of Mathematics, Sigma | ||||||||||||
Publisher: | Cambridge University Press | ||||||||||||
ISSN: | 2050-5094 | ||||||||||||
Official Date: | 31 March 2023 | ||||||||||||
Dates: |
|
||||||||||||
Volume: | 11 | ||||||||||||
Article Number: | e23 | ||||||||||||
DOI: | 10.1017/fms.2023.12 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||
Copyright Holders: | © The Author(s), 2023. Published by Cambridge University Press | ||||||||||||
Date of first compliant deposit: | 3 April 2023 | ||||||||||||
Date of first compliant Open Access: | 3 April 2023 | ||||||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year