  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 path has remained an open problem for several
decades, with asymptotic bounds between $\sqrt{n}$ (Graham and Kleitman, 1973)
and $n/2$ (Calderbank, Chung, and Sturtevant, 1984).
  We consider the average case, when the ordering is chosen uniformly at
random. We discover the surprising result that in the random setting, an
increasing path of the maximum possible length of $n-1$ exists with probability
at least about $1/e$. We also prove that with probability $1-o(1)$, there is an
increasing path of length at least $0.85n$, suggesting that this Hamiltonian
(or near-Hamiltonian) phenomenon may hold asymptotically almost surely.
