Walks on random digraphs (Q1921138)

Let \(D_n\) denote a random directed graph with \(n\) nodes in which each edge is present with independent probability \(c/n\). The limiting probability of the existence in \(D_n\) of a non-reversing path of length \(k\) (that does not contain two edges of the form \(uv\) and \(vu\)) is radically different when \(c< 1\) than when \(c> 1\). The authors portray the threshold at \(c= 1\) as a bifurcation of a certain one-dimensional iteration.