Nearly-linear monotone paths in edge-ordered graphs

Matija Bucić, Matthew Kwan, Alexey Pokrovskiy, Benny Sudakov, Tuan Tran, Adam Zsolt Wagner

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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á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).

Original languageEnglish (US)
Pages (from-to)663-685
Number of pages23
JournalIsrael Journal of Mathematics
Volume238
Issue number2
DOIs
StatePublished - Jul 1 2020
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Nearly-linear monotone paths in edge-ordered graphs'. Together they form a unique fingerprint.

Cite this