A note on correlations in randomly oriented graphs

Abstract

Given a graph $G$, we consider the model where $G$ is given a random orientation by giving each edge a random direction. It is proven that for $a,b,s\in V(G)$, the events $\{s\to a\}$ and $\{s\to b\}$ are positively correlated. This correlation persists, perhaps unexpectedly, also if we first condition on $\{s\nto t\}$ for any vertex $t\ne s$. With this conditioning it is also true that $\{s\to b\}$ and $\{a\to t\}$ are negatively correlated. A concept of increasing events in random orientations is defined and a general inequality corresponding to Harris inequality is given. The results are obtained by combining a very useful lemma by Colin McDiarmid which relates random orientations with edge percolation, with results by van den Berg, Häggström, Kahn on correlation inequalities for edge percolation. The results are true also for another model of randomly directed graphs.

7 pages. The main lemma was first published by Colin McDiarmid. Relevant reference added and text rewritten to reflect this fact

References in corpus (2)

• On percolation and the bunkbed conjecture
• A counter-intuitive correlation in a random tournament

Cited by in corpus (8)

• On percolation and the bunkbed conjecture
• Pure Nash Equilibria and Best-Response Dynamics in Random Games
• A counter-intuitive correlation in a random tournament
• Degenerate random environments
• Correlations for paths in random orientations of G(n,p) and G(n,m)
• Bernoulli trials of fixed parity, random and randomly oriented graphs
• Correlation of paths between distinct vertices in a randomly oriented graph
• Positive association of the oriented percolation cluster in randomly oriented graphs