Monochromatic paths in random tournaments

Matija Bucić; Shoham Letzter; Benny Sudakov

doi:10.1016/j.endm.2017.06.036

Monochromatic paths in random tournaments

Matija Bucić
, Shoham Letzter
, Benny Sudakov

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	177-183
Number of pages	7
Journal	Electronic Notes in Discrete Mathematics
Volume	61
DOIs	https://doi.org/10.1016/j.endm.2017.06.036
State	Published - Aug 2017
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Applied Mathematics

Keywords

Random tournament
Size Ramsey number
directed paths
edge colouring

Access to Document

10.1016/j.endm.2017.06.036

Cite this

@article{72ec1435ed9b4de496e0b4e07534a300,

title = "Monochromatic paths in random tournaments",

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.",

keywords = "Random tournament, Size Ramsey number, directed paths, edge colouring",

author = "Matija Buci{\'c} and Shoham Letzter and Benny Sudakov",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier B.V.",

year = "2017",

month = aug,

doi = "10.1016/j.endm.2017.06.036",

language = "English (US)",

volume = "61",

pages = "177--183",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier BV",

}

TY - JOUR

T1 - Monochromatic paths in random tournaments

AU - Bucić, Matija

AU - Letzter, Shoham

AU - Sudakov, Benny

PY - 2017/8

Y1 - 2017/8

N2 - 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.

AB - 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.

KW - Random tournament

KW - Size Ramsey number

KW - directed paths

KW - edge colouring

UR - https://www.scopus.com/pages/publications/85026769174

UR - https://www.scopus.com/pages/publications/85026769174#tab=citedBy

U2 - 10.1016/j.endm.2017.06.036

DO - 10.1016/j.endm.2017.06.036

M3 - Article

AN - SCOPUS:85026769174

SN - 1571-0653

VL - 61

SP - 177

EP - 183

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Monochromatic paths in random tournaments

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this