Connections in randomly oriented graphs

Abstract

Given an undirected graph $G$, let us randomly orient $G$ by tossing independent (possibly biased) coins, one for each edge of $G$. Writing $a\to b$ for the event that there exists a directed path from a vertex $a$ to a vertex $b$ in such a random orientation, we prove that $\mathbb{P}(s\to a\cap s\to b)\ge \mathbb{P}(s\to a)\mathbb{P}(s\to b)$ for any three vertices $s$, $a$ and $b$ of $G$.

arXiv comment6 pages, Combinatorics, Probability and Computing