#
A counter-intuitive correlation in a random tournament

#### by

## Sven Erick Alm and Svante Linusson

#### Uppsala University and Royal Institute of Technology

##### arXiv:0906.0240

pdf

In * Combinatorics, Probability and Computing* (2011) **20**, 1--9.

### Abstract

Consider a randomly oriented graph $G=(V,E)$ and let $a$, $s$ and $b$ be three distinct vertices in $V$.
We study the correlation between the events $\{a\to s\}$ and $\{s\to b\}$.
We show that, when $G$ is the complete graph $K_n$,
the correlation is negative for $n=3$, zero for $n=4$, and that, counter-intuitively, it is positive for $n\ge5$.
We also show that the correlation is always negative when $G$ is a cycle, $C_n$, and negative or zero when $G$ is a tree (or a forest).

2010-12-06, Sven Erick Alm, sea@math.uu.se