Correlations for paths in random orientations of G(n,p)


Sven Erick Alm and Svante Linusson

Uppsala University and Royal Institute of Technology


Accepted, in extended version, for publication in Random Structures and Algorithms.


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 for a fixed $p<1/2$ the correlation is negative for large enough $n$ and for $p>1/2$ the correlation is positive for large enough $n$. We present exact recursions to compute $P(a\to s)$ and $P(a\to s, s\to b)$. We conjecture that for a fixed $n\ge 27$ the correlation changes sign three times for three critical values of $p$.

2010-10-19, Sven Erick Alm,