Nearly-linear monotone paths in edge-ordered graphs
Bucić M, Kwan MA, Pokrovskiy A, Sudakov B, Tran T, Wagner AZ. 2020. Nearly-linear monotone paths in edge-ordered graphs. Israel Journal of Mathematics. 238(2), 663–685.
Download (ext.)
Journal Article
| Published
| English
Scopus indexed
Author
Bucić, Matija;
Kwan, Matthew AlanISTA 
;
Pokrovskiy, Alexey;
Sudakov, Benny;
Tran, Tuan;
Wagner, Adam Zsolt
;
Pokrovskiy, Alexey;
Sudakov, Benny;
Tran, Tuan;
Wagner, Adam ZsoltAbstract
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átal and Komlós 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 n2/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 n1-o(1).
Publishing Year
Date Published
2020-07-01
Journal Title
Israel Journal of Mathematics
Publisher
Springer
Volume
238
Issue
2
Page
663-685
ISSN
eISSN
IST-REx-ID
Cite this
Bucić M, Kwan MA, Pokrovskiy A, Sudakov B, Tran T, Wagner AZ. Nearly-linear monotone paths in edge-ordered graphs. Israel Journal of Mathematics. 2020;238(2):663-685. doi:10.1007/s11856-020-2035-7
Bucić, M., Kwan, M. A., Pokrovskiy, A., Sudakov, B., Tran, T., & Wagner, A. Z. (2020). Nearly-linear monotone paths in edge-ordered graphs. Israel Journal of Mathematics. Springer. https://doi.org/10.1007/s11856-020-2035-7
Bucić, Matija, Matthew Alan Kwan, Alexey Pokrovskiy, Benny Sudakov, Tuan Tran, and Adam Zsolt Wagner. “Nearly-Linear Monotone Paths in Edge-Ordered Graphs.” Israel Journal of Mathematics. Springer, 2020. https://doi.org/10.1007/s11856-020-2035-7.
M. Bucić, M. A. Kwan, A. Pokrovskiy, B. Sudakov, T. Tran, and A. Z. Wagner, “Nearly-linear monotone paths in edge-ordered graphs,” Israel Journal of Mathematics, vol. 238, no. 2. Springer, pp. 663–685, 2020.
Bucić M, Kwan MA, Pokrovskiy A, Sudakov B, Tran T, Wagner AZ. 2020. Nearly-linear monotone paths in edge-ordered graphs. Israel Journal of Mathematics. 238(2), 663–685.
Bucić, Matija, et al. “Nearly-Linear Monotone Paths in Edge-Ordered Graphs.” Israel Journal of Mathematics, vol. 238, no. 2, Springer, 2020, pp. 663–85, doi:10.1007/s11856-020-2035-7.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1809.01468
Google Scholar