First critical probability for a problem on random orientations in \(G(n,p)\). (English) Zbl 1300.05279

Alm, Sven Erick; Janson, Svante; Linusson, Svante

Electron. J. Probab. 19, Paper No. 69, 14 p. (2014).

Summary: We study the random graph \(G(n,p)\) with a random orientation. For three fixed vertices \(s\), \(a\), \(b\) in \(G(n,p)\) we study the correlation of the events \(\{a\to s\}\) (there exists a directed path from \(a\) to \(s\)) and \(\{s\to b\}\). We prove that asymptotically the correlation is negative for small \(p\), \(p<\frac{C_1}n\), where \(C_1\approx0.3617\), positive for \(\frac{C_1}n<p<\frac2n\) and up to \(p=p_2(n)\). Computer aided computations suggest that \(p_2(n)=\frac{C_2}n\), with \(C_2\approx 7.5\). We conjecture that the correlation then stays negative for \(p\) up to the previously known zero at \(\frac12\); for larger \(p\) it is positive.

MSC:

05C80	Random graphs (graph-theoretic aspects)
05C20	Directed graphs (digraphs), tournaments
05C38	Paths and cycles
60C05	Combinatorial probability

Keywords:

random directed graphs; correlation; directed paths