Monochromatic paths in random tournaments

Matija Bucić, Shoham Letzter, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


We prove that, with high probability, any 2-edge-coloring of a random tournament on n vertices contains a monochromatic path of length Ω(n/√logn). 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.

Original languageEnglish (US)
Pages (from-to)69-81
Number of pages13
JournalRandom Structures and Algorithms
Issue number1
StatePublished - Jan 2019
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


  • Ramsey theory
  • monochromatic directed path
  • monochromatic oriented path
  • size Ramsey number


Dive into the research topics of 'Monochromatic paths in random tournaments'. Together they form a unique fingerprint.

Cite this