Stability for the Erdős-Rothschild problem

Pikhurko, Oleg and Staden, Katherine (2023). Stability for the Erdős-Rothschild problem. Forum of Mathematics, Sigma, 11, article no. e23.

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

Abstract

Given a sequence $\bm{k} := (k_1,\ldots,k_s)$ of natural numbers and 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. This problem was first considered by Erd\H{o}s and Rothschild in 1974, but it has been solved only for a very small number of non-trivial cases. In previous work with Yilma, we constructed a finite optimisation problem whose maximum is equal to the limit of $\log_2 F(n;\bm{k})/{n\choose 2}$ as $n$ tends to infinity and proved a stability theorem for complete multipartite graphs $G$.

In this paper we provide a sufficient condition on $\bm{k}$ which guarantees a general stability theorem for \emph{any} graph $G$, describing the asymptotic structure of $G$ on $n$ vertices with $F(G;\bm{k}) = F(n;\bm{k}) \cdot 2^{o(n^2)}$ in terms of solutions to the optimisation problem. We apply our theorem to systematically recover existing stability results as well as all cases with $s=2$. The proof uses a version of symmetrisation on edge-coloured weighted multigraphs.

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)