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.