The threshold conjecture for arbitrary oriented Hamilton cycles in random digraphs

Let DD(n,p)D\sim\mathcal D(n,p) be a random directed graph on vertex set [n][n], where each possible arc is present independently with probability pp, and let CC be a Hamilton cycle with an arbitrary orientation. Threshold conjecture for arbitrary oriented Hamilton cycles. If

p=lnn+ω(1)n,p=\frac{\ln n+\omega(1)}{n},

then DD contains a copy of CC with high probability. This conjecture seeks the exact appearance threshold for an arbitrary oriented Hamilton cycle; the corresponding threshold for consistently oriented Hamilton cycles is known, while the arbitrary-orientation case is presented here as open.

Sources & referencesView supporting material

Primary source

Asaf Ferber and Eoin Long, “Packing and counting arbitrary Hamilton cycles in random digraphs”, arXiv:1603.03614 (2016).

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.