Bucić, M;
Letzter, S;
Sudakov, B;
(2019)
Monochromatic paths in random tournaments.
Random Structures & Algorithms
, 54
(1)
pp. 69-81.
10.1002/rsa.20780.
Preview |
Text
random-tournament-ramsey.pdf - Accepted Version Download (314kB) | Preview |
Abstract
We prove that, with high probability, any 2‐edge‐coloring of a random tournament on n vertices contains a monochromatic path of length \Omega(n/ \sqrt{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.
| Type: | Article |
|---|---|
| Title: | Monochromatic paths in random tournaments |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1002/rsa.20780 |
| Publisher version: | https://doi.org/10.1002/rsa.20780 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher's terms and conditions. |
| Keywords: | monochromatic directed path, monochromatic oriented path, Ramsey theory, size Ramsey number |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10107274 |
Archive Staff Only
 |
View Item |
