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

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.


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