A note on correlations in randomly oriented graphs
| dc.creator | Linusson, Svante | |
| dc.date | 2009-05-18 | |
| dc.date | 2009-05-24 | |
| dc.date.accessioned | 2026-07-07T13:17:19Z | |
| dc.date.available | 2026-07-07T13:17:19Z | |
| dc.description | 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äggström, Kahn on correlation inequalities for edge percolation. The results are true also for another model of randomly directed graphs. | |
| dc.description | 7 pages. The main lemma was first published by Colin McDiarmid. Relevant reference added and text rewritten to reflect this fact | |
| dc.identifier | https://arxiv.org/abs/0905.2881 | |
| dc.identifier | http://arxiv.org/abs/0905.2881 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/231075 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.subject | 05C80; 60C05;60K35 | |
| dc.title | A note on correlations in randomly oriented graphs | |
| dc.type | text |