# 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

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.
2014-08-18, Sven Erick Alm, sea@math.uu.se