Hamilton cycles in a class of random directed graphs (Q1333332)

This paper is the latest in a long line investigating thresholds for a random graph or digraph to have a Hamiltonian cycle. The random digraph \(D_{k- in,l-out}\) is defined as follows: it has vertices \(1,2,\dots, n\), and each vertex \(v\) chooses, independently and uniformly at random, \(k\) arcs \(xv\) and \(l\) arcs \(vy\). It is shown that, with probability tending to 1 as \(n\to \infty\), the random digraph \(D_{3- in,3-out}\) is Hamiltonian. [The quest continues to show that \(D_{2- in,2-out}\) is Hamiltonian.] The idea of the proof is to consider \(D_{3-in,3-out}\) as the union of two random digraphs \(D_ a\) and \(D_ b\); observe from previous results that in \(D_ a\) there is usually a permutation digraph with not too many cycles; use arcs from \(D_ b\) to try to increase the minimum cycle length; and finally to cut up these long cycles and try to rejoin them to form a Hamiltonian cycle, again using arcs of \(D_ b\).