Lavrov–Loh conjecture on Hamiltonian monotone paths in random edge-orderings
Lavrov–Loh conjecture on Hamiltonian monotone paths in random edge-orderings
Let be the complete graph on vertices, choose an edge-ordering of uniformly at random, and call a path Hamiltonian if it contains all vertices of . A path is monotone when it traverses edges in increasing order in the edge-ordering.
Lavrov–Loh conjecture. With probability tending to as , a random edge-ordering of contains a Hamiltonian monotone path.
The conjecture strengthens the result that the probability is at least . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.