Mathematics – Probability
Scientific paper
2009-05-18
Mathematics
Probability
7 pages. The main lemma was first published by Colin McDiarmid. Relevant reference added and text rewritten to reflect this fa
Scientific paper
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\neq 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\"aggstr\"om, Kahn on correlation inequalities for edge percolation. The results are true also for another model of randomly directed graphs.
No associations
LandOfFree
A note on correlations in randomly oriented graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A note on correlations in randomly oriented graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A note on correlations in randomly oriented graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-609622