2020/02/06 by Chris Lambie‐Hanson, Lambie-Hanson, Chris, Dániel T. Soukup +1
Mathematics · #03E02 #03E05 #05C63 #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Logic (math.LO)
paper · pdf · doi:10.48550/arxiv.2002.02480
openalex publication_date 2020/02/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The optimality of the Erd Hos-Rado theorem for pairs is witnessed by the\ncolouring \Δ_\κ : [2^\κ]2 \→ \κ recording the least\npoint of disagreement between two functions. This colouring has no\nmonochromatic triangles or, more generally, odd cycles. We investigate a number\nof questions investigating the extent to which \Δ_\κ is an\n\extremal such triangle-free or odd-cycle-free colouring. We begin by\nintroducing the notion of \Δ-regressive and almost \Δ-regressive\ncolourings and studying the structures that must appear as monochromatic\nsubgraphs for such colourings. We also consider the question as to whether\n\Δ_\κ has the minimal cardinality of any \maximal triangle-free\nor odd-cycle-free colouring into \κ. We resolve the question positively\nfor odd-cycle-free colourings.\n