2014/05/26 by Shoham Letzter
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics #Complete graph #Computer science #Constant (computer programming) #Discrete mathematics #Enhanced Data Rates for GSM Evolution #Graph #Limits and Structures in Graph Theory #Mathematics #Monochromatic color #Optics #Path (computing) #Path length #Physics #Ramsey's theorem #Random graph #Telecommunications #math.CO #msc:05C80 #msc:05D10
paper · pdf · doi:10.1017/s0963548315000279
published as Combinator. Probab. Comp. 25 (2016) 612-622
arxiv created 2014/05/26 · openalex publication_date 2015/12/07 · arxiv updated 2019/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Answering a question raised by Dudek and Prałat, we show that if pn → ∞, w.h.p., whenever G = G ( n, p ) is 2-edge-coloured there is a monochromatic path of length (2/3 + o (1)) n . This result is optimal in the sense that 2/3 cannot be replaced by a larger constant. As part of the proof we obtain the following result. Given a graph G on n vertices with at least (1-ε)\binomn2 edges, whenever G is 2-edge-coloured, there is a monochromatic path of length at least (2/3 - 110√(ε))n . This is an extension of the classical result by Gerencsér and Gyárfás which says that whenever K n is 2-coloured there is a monochromatic path of length at least 2 n /3.