Exact solutions to the Erdős-Rothschild problem

DOI10.1017/FMS.2023.117zbMATH Open1530.05096arXiv2108.12789OpenAlexW4390667292MaRDI QIDQ6178441FDOQ6178441

Authors: Oleg Pikhurko, Katherine Staden 

Publication date: 18 January 2024

Published in: Forum of Mathematics, Sigma (Search for Journal in Brave)

Abstract: Let $extbfk:=(k_1,ldots,k_s)$ be a sequence of natural numbers. For a graph $G$, let $F(G;extbfk)$ denote the number of colourings of the edges of $G$ with colours $1,dots,s$ such that, for every $cin1,dots,s$, the edges of colour $c$ contain no clique of order $k_c$. Write $F(n;extbfk)$ to denote the maximum of $F(G;extbfk)$ over all graphs $G$ on $n$ vertices. There are currently very few known exact (or asymptotic) results known for this problem, posed by ErdH{o}s and Rothschild in 1974. We prove some new exact results for $noinfty$: (i) A sufficient condition on $extbfk$ which guarantees that every extremal graph is a complete multipartite graph, which systematically recovers all existing exact results. (ii) Addressing the original question of ErdH{o}s and Rothschild, in the case $extbfk=(3,ldots,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 $extbfk=(k+1,k)$, for which the sufficient condition in (i) does not hold, for $3leqkleq10$, 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.

Full work available at URL: https://arxiv.org/abs/2108.12789

Recommendations

• The Erdős–Rothschild problem on edge-colourings with forbidden monochromatic cliques
• Stability for the Erdős-Rothschild problem
• A rainbow Erdös-Rothschild problem
• An extension of the rainbow Erdős-Rothschild problem
• A rainbow Erdős-Rothschild problem

zbMATH Keywords

complete multipartite graphHadamard matrices

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• The maximum number of \(K_{3}\)-free and \(K_{4}\)-free edge 4-colorings
• Title not available (Why is that?)
• THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
• Stability for the Erdős-Rothschild problem
• Title not available (Why is that?)
• A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity
• Title not available (Why is that?)
• The Erdős–Rothschild problem on edge-colourings with forbidden monochromatic cliques

Cited In (1)

• Edge-colorings avoiding patterns in a triangle

This page was built for publication: Exact solutions to the Erdős-Rothschild problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6178441)