2018/03/31 by Shagnik Das, Roman Glebov, Benny Sudakov +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Antichain #Combinatorics #Complete graph #Discrete mathematics #Graph #Limits and Structures in Graph Theory #Mathematics #Monochromatic color #Partially ordered set #Physics #Ramsey's theorem #Rothschild #Vertex (graph theory) #math.CO
paper · pdf · doi:10.1016/j.jcta.2019.05.014
30 pages, final version
arxiv created 2019/06/08 · arxiv updated 2019/06/11 · openalex publication_date 2019/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
A coloured version of classic extremal problems dates back to Erdős and Rothschild, who in 1974 asked which n-vertex graph has the maximum number of 2-edge-colourings without monochromatic triangles. They conjectured that the answer is simply given by the largest triangle-free graph. Since then, this new class of coloured extremal problems has been extensively studied by various researchers. In this paper we pursue the Erdős--Rothschild versions of Sperner's Theorem, the classic result in extremal set theory on the size of the largest antichain in the Boolean lattice, and Erdős' extension to k-chain-free families. Given a family F of subsets of [n], we define an (r,k)-colouring of F to be an r-colouring of the sets without any monochromatic k-chains F1 ⊂ F2 ⊂ … ⊂ Fk. We prove that for n sufficiently large in terms of k, the largest k-chain-free families also maximise the number of (2,k)-colourings. We also show that the middle level, \binom[n]\lfloor n/2 \rfloor, maximises the number of (3,2)-colourings, and give asymptotic results on the maximum possible number of (r,k)-colourings whenever r(k-1) is divisible by three.