Correlations for paths in random orientations of G(n,p)
by
Sven Erick Alm and Svante Linusson
Uppsala University and Royal Institute of Technology
arXiv:0906.0720v1
pdf
Accepted, in extended version, for publication in Random Structures and Algorithms.
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\}$ 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$.