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

2010-10-19, Sven Erick Alm, sea@math.uu.se