The Library
Exact solutions for the Erdos-Rothschild problem
Tools
Pikhurko, O. and Staden, K. (2024) Exact solutions for the Erdos-Rothschild problem. Forum of Mathematics, Sigma, 12 . e8. doi:10.1017/fms.2023.117 ISSN 2050-5094 .
|
PDF
exact-solutions-to-the-erdos-rothschild-problem.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (680Kb) | Preview |
|
|
PDF
WRAP-exact-solutions-Erdos-Rothschild-problem-Pikhurko-2023.pdf - Accepted Version - Requires a PDF viewer. Download (585Kb) | Preview |
Official URL: https://doi.org/10.1017/fms.2023.117
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. 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.
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, Combinatorial analysis | ||||||||||||
Journal or Publication Title: | Forum of Mathematics, Sigma | ||||||||||||
Publisher: | Cambridge University Press | ||||||||||||
ISSN: | 2050-5094 | ||||||||||||
Official Date: | 2024 | ||||||||||||
Dates: |
|
||||||||||||
Volume: | 12 | ||||||||||||
Article Number: | e8 | ||||||||||||
DOI: | 10.1017/fms.2023.117 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||
Copyright Holders: | © The Author(s), 2024. Published by Cambridge University Press | ||||||||||||
Date of first compliant deposit: | 16 November 2023 | ||||||||||||
Date of first compliant Open Access: | 20 November 2023 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year