A Counter-Intuitive Correlation in a Random Tournament

Source 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 → s } and { s → b }. We show that, counter-intuitively, when G is the complete graph K n , n ≥ 5, then the correlation is positive. (It is negative for n = 3 and zero for n = 4.) We briefly discuss and pose problems for the same question on other graphs.