Exact solutions to the Erdős-Rothschild problem

DOI10.1017/FMS.2023.117MaRDI QIDQ6178441zbMATH OpenOpenAlexFDO

Authors Oleg Pikhurko, Katherine Staden

Publication date 18 January 2024

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 426159 (Why is no real title available?)
• scientific article; zbMATH DE number 3487496 (Why is no real title available?)
• scientific article; zbMATH DE number 554066 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity
• Stability for the Erdős-Rothschild problem
• THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
• The Erdős–Rothschild problem on edge-colourings with forbidden monochromatic cliques
• The maximum number of \(K_{3}\)-free and \(K_{4}\)-free edge 4-colorings

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)