Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-23T23:51:58.553Z Has data issue: false hasContentIssue false
  • English
  • Français

Positive association of the oriented percolation cluster in randomly oriented graphs

Part of: Graph theory Equilibrium statistical mechanics Combinatorial probability Special processes

Published online by Cambridge University Press:  08 July 2019

François Bienvenu
François Bienvenu*
Affiliation:
Center for Interdisciplinary Research in Biology (CIRB), CNRS UMR 7241, Collège de France, Paris, France Laboratoire de Probabilités, Statistique et Modélisation (LPSM), CNRS UMR 8001, Sorbonne Université, Paris, France
*
(Email: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Consider any fixed graph whose edges have been randomly and independently oriented, and write {S ⇝} to indicate that there is an oriented path going from a vertex s ∊ S to vertex i. Narayanan (2016) proved that for any set S and any two vertices i and j, {S ⇝ i} and {S ⇝ 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 ⇝ i}, i ∊ V, are positively associated, meaning that the expectation of the product of increasing functionals of the family {S ⇝ i} for i ∊ V is greater than the product of their expectations.

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 60K35: Interacting random processes; statistical mechanics type models; percolation theory 82B43: Percolation 05C80: Random graphs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Issue 6 , November 2019 , pp. 811 - 815
Copyright
© Cambridge University Press 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ahlswede, R. and Daykin, D. E. (1978) An inequality for the weights of two families of sets, their unions and intersections. Probab. Theory Related Fields 43 183–185.Google Scholar
Barbour, A. D., Holst, L. and Janson, S. (1992) Poisson Approximation, Oxford Studies in Probability, Oxford University Press.Google Scholar
Durrett, R. (1984) Oriented percolation in two dimensions. Ann. Probab. 12 999–1040.CrossRefGoogle Scholar
Esary, J. D., Proschan, F. and Walkup, D. W. (1967) Association of random variables, with applications. Ann. Math. Statist. 38 1466–1474.CrossRefGoogle Scholar
Fill, J. A. and Pemantle, R. (1993) Percolation, first-passage percolation and covering times for Richardson’s model on the n-cube. Ann. Appl. Probab. 3 593–629.CrossRefGoogle Scholar
Fortuin, C. M., Kasteleyn, P. W. and Ginibre, J. (1971) Correlation inequalities on some partially ordered sets. Commun. Math. Phys. 22 89–103.CrossRefGoogle Scholar
Linusson, S. (2009) A note on correlations in randomly oriented graphs. arXiv:0905.2881Google Scholar
Narayanan, B. (2018) Connections in randomly oriented graphs. Combin. Probab. Comput. 27 667–671.CrossRefGoogle Scholar
Ross, N. (2011) Fundamentals of Stein’s method. Probab. Surv. 8 201–293.CrossRefGoogle Scholar