Monochromatic paths in random tournaments

Matija Bucić; Shoham Letzter; Benny Sudakov

doi:10.1002/rsa.20780

Monochromatic paths in random tournaments

Matija Bucić, Shoham Letzter, Benny Sudakov

Research output: Contribution to journal › Article › peer-review

9 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 language	English (US)
Pages (from-to)	69-81
Number of pages	13
Journal	Random Structures and Algorithms
Volume	54
Issue number	1
DOIs	https://doi.org/10.1002/rsa.20780
State	Published - Jan 2019
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Keywords

Ramsey theory
monochromatic directed path
monochromatic oriented path
size Ramsey number

Access to Document

10.1002/rsa.20780

Cite this

@article{6d978992dac34bbe986ab74fb7e06293,

title = "Monochromatic paths in random tournaments",

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

keywords = "Ramsey theory, monochromatic directed path, monochromatic oriented path, size Ramsey number",

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

note = "Publisher Copyright: {\textcopyright} 2018 Wiley Periodicals, Inc.",

year = "2019",

month = jan,

doi = "10.1002/rsa.20780",

language = "English (US)",

volume = "54",

pages = "69--81",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "1",

}

TY - JOUR

T1 - Monochromatic paths in random tournaments

AU - Bucić, Matija

AU - Letzter, Shoham

AU - Sudakov, Benny

PY - 2019/1

Y1 - 2019/1

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

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

KW - Ramsey theory

KW - monochromatic directed path

KW - monochromatic oriented path

KW - size Ramsey number

UR - http://www.scopus.com/inward/record.url?scp=85044941366&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85044941366&partnerID=8YFLogxK

U2 - 10.1002/rsa.20780

DO - 10.1002/rsa.20780

M3 - Article

AN - SCOPUS:85044941366

SN - 1042-9832

VL - 54

SP - 69

EP - 81

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 1

ER -

Monochromatic paths in random tournaments

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this