SMILE

Stochastic Models for the Inference of Life Evolution

Positive association of the oriented percolation cluster in randomly oriented graphs

Bienvenu, F.

Combinatorics, Probability and Computing

2019

Consider any fixed graph whose edges have been randomly and independently oriented, and write \(\{S \leadsto i\}\) to indicate that there is an oriented path going from a vertex \(s \in S\) to vertex \(i\). Narayanan (2016) proved that for any set \(S\) and any two vertices \(i\) and \(j\), \(\{S \leadsto i\}\) and \(\{S \leadsto j\}\) are positively correlated. His proof relies on the Ahlswede-Daykin inequality, a rather advanced tool of probabilistic combinatorics. In this short note, I give an elementary proof of the following, stronger result: writing \(V\) for the vertex set of the graph, for any source set \(S\), the events \(\{S \leadsto i\}\), \(i \in V\), are positively associated -- meaning that the expectation of the product of increasing functionals of the family \(\{S \leadsto i\}\) for \(i \in V\) is greater than the product of their expectations.

Bibtex

@article{Bienvenu2017PercoRandomlyOriented,
author = {Bienvenu, Fran{\c{c}}ois},
title = {Positive association of the oriented percolation cluster in randomly oriented graphs},
journal = {Combinatorics, Probability and Computing},
volume = {28},
number = {6},
pages = {811--815}
year = {2019},
doi = {10.1017/S0963548319000191}
}

Link to the article

Accéder à l'article grâce à son DOI.
View the PDF.