Monochromatic paths in random tournaments

Matija Bucić, Shoham Letzter, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

Abstract

We prove that, with high probability, any 2-edge colouring 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.

Original languageEnglish (US)
Pages (from-to)177-183
Number of pages7
JournalElectronic Notes in Discrete Mathematics
Volume61
DOIs
StatePublished - Aug 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Keywords

  • Random tournament
  • Size Ramsey number
  • directed paths
  • edge colouring

Fingerprint

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

Cite this