On the existence of Hamilton cycles with a periodic pattern in a random digraph

Alan Frieze, Xavier Perez-Gimenez, Pawel Pralat

Published 2020-02-18Version 1

We consider Hamilton cycles in the random digraph $D_{n,m}$ where the orientation of edges follows a pattern other than the trivial orientation in which the edges are oriented in the same direction as we traverse the cycle. We show that if the orientation forms a periodic pattern, other than the trivial pattern, then approximately half the usual $n\log n$ edges are needed to guarantee the existence of such Hamilton cycles a.a.s.