Nearly-linear monotone paths in edge-ordered graphs

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