First critical probability for a problem on random orientations in G(n,p)
by
Sven Erick Alm, Svante Janson and Svante Linusson
Uppsala University, Uppsala University and Royal Institute of Technology
pdf
In Electronic Journal of Probability Vol. 19, Article 69.
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\}$ (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.