BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Nearly-linear monotone paths in edge-ordered graphs Bucic, Matija


How long a monotone path can one always find in any edge-ordering of the complete graph $K_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 was $n^{2/3-o(1)}$. We almost close this gap, proving that any edge-ordering of the complete graph contains a monotone path of length $n^{1-o(1)}$. This is joint work with Matthew Kwan, Alexey Pokrovskiy, Benny Sudakov, Tuan Tran and Adam Wagner.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International