# 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.

2014-08-18, Sven Erick Alm, sea@math.uu.se