Open Access Open Access  Restricted Access Subscription Access

Correlation of Paths Between Distinct Vertices in a Randomly Oriented Graph

Madeleine Leander, Svante Linusson


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.

Full Text:




  • There are currently no refbacks.
This website uses cookies to allow us to see how the site is used. The cookies cannot identify you or any content at your own computer.

ISSN 0025-5521 (print) ISSN 1903-1807 (online)

Hosted by the Royal Danish Library