Correlation of paths between distinct vertices in a randomly oriented graph

Abstract

We prove that in a random tournament the events $\{s\to a\}$ and $\{t\to b\}$ are positively correlated, for distinct vertices $a,s,b,t\in K_n.$ It is also proven that the correlation between the events $\{s\to a\}$ and $\{t\to b\}$ in the random graphs $G(n,p)$ and $G(n,m)$ with random orientation is positive for every fixed $p>0$ and sufficiently large $n$ (with $m=\lfloor p\left(\genfrac{}{}{0ex}{}{n}{2}\right)\rfloor$). We conjecture it to be positive for all $p$ and all $n$. An exact recursion for $\P (\{s\to a\}\cap \{t\to b\})$ in $\gnp$ is given.

12 pages, 3 figures

References in corpus (1)

• A note on correlations in randomly oriented graphs