First critical probability for a problem on random orientations in $G(n,p)$

Abstract

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$ and $s\to b$. We prove that asymptotically the correlation is negative for small $p$, $p<\frac{C_1}{n}$, where $C_1\approx 0.3617$, positive for $\frac{C_1}{n}<p<\frac{2}{n}$ 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 $\frac{1}{2}$; for larger $p$ it is positive.

15 pages, 3 figures