2025/01/06 by Eden Kuperwasser, Kuperwasser, Eden
Mathematics · #05C80 #05D10 #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2501.03439
openalex publication_date 2025/01/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We say that a graph G is anti-Ramsey for a graph H if any proper edge-colouring of G yields a rainbow copy of H, i.e. a copy of H whose edges all receive different colours. In this work we determine the threshold at which the binomial random graph becomes anti-Ramsey for any fixed graph H, given that H is sufficiently dense. Our proof employs a graph decomposition lemma in the style of the Nine Dragon Tree theorem that may be of independent interest.