UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Nearly-linear monotone paths in edge-ordered graphs

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.

[img] Text
1809.01468.pdf - Accepted version
Access restricted to UCL open access staff until 8 July 2021.

Download (232kB)

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
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 > 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
Downloads since deposit
1Download
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item