Stability for the Erdős-Rothschild problem

Journal article

Given a sequence $\boldsymbol {k} := (k_1,\ldots ,k_s)$ of natural numbers and a graph G, let $F(G;\boldsymbol {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;\boldsymbol {k})$ to denote the maximum of $F(G;\boldsymbol {k})$ over all graphs G on n vertices. This problem was first considered by Erdős and Rothschild in 1974, but it has been solved only for a very small number of nontrivial cases. In previous work with Pikhurko and Yilma, (Math. Proc. Cambridge Phil. Soc. 163 (2017), 341–356), we constructed a finite optimisation problem whose maximum is equal to the limit of $\log _2 F(n;\boldsymbol {k})/{n\choose 2}$ as n tends to infinity and proved a stability theorem for complete multipartite graphs G

Authors: Pikhurko, O; Staden, K

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Cambridge University Press
• Journal: Forum of Mathematics, Sigma
• Volume: 11
• Pages: e23
• Publication date: 2023-03-31
• DOI: 10.1017/fms.2023.12
• EISSN: 2050-5094
• ISSN: 2050-5094
• Language: English
• Keywords: Physics; Combinatorics; Rothschild; Mathematics; Mathematical analysis; Multipartite; Graph; Infinity; Discrete mathematics; Quantum mechanics