Correlation of Paths Between Distinct Vertices in a Randomly Oriented Graph

Authors

  • Madeleine Leander
  • Svante Linusson

DOI:

https://doi.org/10.7146/math.scand.a-21163

Abstract

We prove that in a random tournament the events $\{s\rightarrow a\}$ (meaning that there is a directed path from $s$ to $a$) and $\{t\rightarrow 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\rightarrow a\}$ and $\{t\rightarrow 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=\bigl\lfloor p \binom{n}{2}\bigr\rfloor$). We conjecture it to be positive for all $p$ and all $n$. An exact recursion for $\mathsf{P}(\{s\rightarrow a\} \cap \{t\rightarrow b\})$ in $G(n,p)$ is given.

Downloads

Published

2015-06-26

How to Cite

Leander, M., & Linusson, S. (2015). Correlation of Paths Between Distinct Vertices in a Randomly Oriented Graph. MATHEMATICA SCANDINAVICA, 116(2), 287–300. https://doi.org/10.7146/math.scand.a-21163

Issue

Section

Articles