Lavrov–Loh conjecture on Hamiltonian monotone paths in random edge-orderings

Let KnK_n be the complete graph on nn vertices, choose an edge-ordering of KnK_n uniformly at random, and call a path Hamiltonian if it contains all vertices of KnK_n. A path is monotone when it traverses edges in increasing order in the edge-ordering.

Lavrov–Loh conjecture. With probability tending to 11 as nn\to\infty, a random edge-ordering of KnK_n contains a Hamiltonian monotone path.

The conjecture strengthens the result that the probability is at least 1/eo(1)1/e-o(1). It asks whether Hamiltonian monotone paths occur with asymptotically overwhelming probability; the source gives no resolution.

Sources & referencesView supporting material

Primary source

Kevin G. Milans, “Monotone Paths in Dense Edge-Ordered Graphs”, arXiv:1509.02143 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.