Monochromatic paths in random tournaments. Issue 1 (6th April 2018)

• Record Type: Journal Article
• Authors: Bucić, Matija; Letzter, Shoham; Sudakov, Benny
• Is Part Of: Random structures & algorithms. Volume 54:Issue 1(2019)
• Page Start: 69
• Page End: 81
• Publication Date: 2018-04-06
• Subjects: monochromatic directed path -- monochromatic oriented path -- Ramsey theory -- size Ramsey number; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20780
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We prove that, with high probability, any 2‐edge‐coloring of a random tournament on n vertices contains a monochromatic path of length Ω ( n / log ⁡ n ) . This resolves a conjecture of Ben‐Eliezer, Krivelevich, and Sudakov and implies a nearly tight upper bound on the oriented size Ramsey number of a directed path.