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


Sven Erick Alm, Svante Janson and Svante Linusson

Uppsala University, Uppsala University and Royal Institute of Technology


In Electronic Journal of Probability Vol. 19, Article 69.


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 $a4 to $s$) and $\{s\to b\}$. We prove that asymptotically the correlation is negative for small $p$, $p< C_1/n$, where $C_1\approx0.3617$, positive for $C_1/n< p<2/n$ and up to $p=p_2(n)$. Computer aided computations suggest that $p_2(n)=C_2/n$, with $C_2\approx7.5$. We conjecture that the correlation then stays negative for $p$ up to the previously known zero at 1/2; for larger $p$ it is positive.

2014-08-18, Sven Erick Alm,