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

## Sven Erick Alm, Svante Janson and Svante Linusson

#### Uppsala University, Uppsala University and Royal Institute of Technology

pdf

In Random Structures and Algorithms Vol. 39, Issue 4, 486-506 (2011).
pdf

### Abstract

We study random graphs, both $G(n,p)$ and $G(n,m)$, with random orientations on the edges. For three fixed distinct vertices $s,a,b$ we study the correlation, in the combined probability space, of the events $\{a\to s\}$ and $\{s\to b\}$.
For $\gnp$, we prove that there is a $\pc=1/2$ such that for a fixed $p<\pc$ the correlation is negative for large enough $n$ and for $p>\pc$ the correlation is positive for large enough $n$. %For $G(n,p)$ it is proved that $\pc=1/2$ and We conjecture that for a fixed $n\ge 27$ the correlation changes sign three times for three critical values of $p$.
For $G(n,m)$ it is similarly proved that, with $p=m/\binom{n}{2}$, there is a critical $\pc$ that is the solution to a certain equation and approximately equal to 0.7993. A lemma, which computes the probability of non existence of any $\ell$ directed edges in $\gnm$, is thought to be of independent interest.
We present exact recursions to compute $\P(a\to s)$ and $\P(a\to s, s\to b)$. We also briefly discuss the corresponding question in the quenched version of the problem.
2014-08-18, Sven Erick Alm, sea@math.uu.se