Hamiltonian increasing paths in random edge orderings

Mikhail Lavrov, Po-Shen Loh

If the edges of the complete graph $K_n$ are totally ordered, a simple path whose edges are in ascending order is called increasing. The worst-case length of the longest increasing…