Bucic, M;
Kwan, M;
Pokrovskiy, A;
Sudakov, B;
Tran, T;
Wagner, AZ;
(2020)
Nearly-linear monotone paths in edge-ordered graphs.
Israel Journal of Mathematics
, 238
pp. 663-685.
10.1007/s11856-020-2035-7.
Preview |
Text
1809.01468.pdf - Accepted Version Download (232kB) | Preview |
Abstract
How long a monotone path can one always find in any edge-ordering of the complete graph Kn? This appealing question was first asked by Chv´atal and Koml´os in 1971, and has since attracted the attention of many researchers, inspiring a variety of related problems. The prevailing conjecture is that one can always find a monotone path of linear length, but until now the best known lower bound was n 2/3−o(1). In this paper we almost close this gap, proving that any edge-ordering of the complete graph contains a monotone path of length n 1−o(1)
| Type: | Article |
|---|---|
| Title: | Nearly-linear monotone paths in edge-ordered graphs |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/s11856-020-2035-7 |
| Publisher version: | https://doi.org/10.1007/s11856-020-2035-7 |
| 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. |
| 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.ucl.ac.uk/id/eprint/10112636 |
Archive Staff Only
 |
View Item |
