Exact solutions to the Erdős-Rothschild problem

Journal article

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

Authors: Pikhurko, O; Staden, K

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Cambridge University Press
• Journal: Forum of Mathematics, Sigma
• Volume: 12
• Pages: e8
• Publication date: 2024-01-08
• DOI: 10.1017/fms.2023.117
• EISSN: 2050-5094
• ISSN: 2050-5094
• Language: English
• Keywords: Complete graph; Mathematics; Combinatorics; Order (exchange); Quantum mechanics; Physics; Discrete mathematics; Graph; Multipartite; Rothschild