- Journal Article
How long a monotone path can one always find in any edge-ordering of the complete graphK(n)? This appealing question was first asked by Chvatal and Komlos 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 wasn(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 lengthn(1-o(1)). Show more
Journal / seriesIsrael Journal of Mathematics
Pages / Article No.
PublisherHebrew University Magnes Press
Organisational unit03993 - Sudakov, Benjamin / Sudakov, Benjamin
175573 - Extremal problems in combinatorics (SNF)
MoreShow all metadata