Monochromatic paths in random tournaments

Matija Bucić, Shoham Letzter, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

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/√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
Volume54
Issue number1
DOIs
StatePublished - Jan 2019
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Keywords

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

Fingerprint

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

Cite this