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

#### by

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