Exact results for the Erdős-Rothschild problem

Pikhurko, Oleg and Staden, Katherine (2024). Exact results for the Erdős-Rothschild problem. Forum of Mathematics, Sigma, 12, article no. e8.

DOI: https://doi.org/10.1017/fms.2023.117

Abstract

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.

Viewing alternatives

Look up in Google Scholar

Download history

Metrics

Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions

Export

About

CORE (COnnecting REpositories)