Given a graph G and a bijection f : E(G)\rightarrow \{1, 2, \ldots,e(G)\}, we say that a trail/path in G is f-\emph{increasing} if the labels of consecutive edges of this trail/path form an increasing sequence. More than 40 years ago Chv\'atal and Koml\'os raised the question of providing the worst-case estimates of the length of the longest increasing trail/path over all edge orderings of Kn. The case of a trail was resolved by Graham and Kleitman, who proved that the answer is n−1, and the case of a path is still widely open. Recently Lavrov and Loh proposed to study the average case of this problem in which the edge ordering is chosen uniformly at random. They conjectured (and it was proved by Martinsson) that such an ordering with high probability (whp) contains an increasing Hamilton path.
