Positive association of the oriented percolation cluster in randomly oriented graphs

DOI10.1017/S0963548319000191zbMATH Open1434.60033arXiv1711.08815WikidataQ127589723 ScholiaQ127589723MaRDI QIDQ5222557FDOQ5222557

Authors: François Bienvenu 

Publication date: 6 April 2020

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1711.08815

Recommendations

• Correlation of Paths Between Distinct Vertices in a Randomly Oriented Graph
• Connections in randomly oriented graphs
• First critical probability for a problem on random orientations in \(G(n,p)\).
• Correlations for paths in random orientations of \(G(n,p)\) and \(G(n,m)\)
• Some conditional correlation inequalities for percolation and related processes

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05) Percolation (82B43)

Cites Work

• Association of Random Variables, with Applications
• Title not available (Why is that?)
• Fundamentals of Stein's method
• Oriented percolation in two dimensions
• Correlation inequalities on some partially ordered sets
• An inequality for the weights of two families of sets, their unions and intersections
• Percolation, first-passage percolation and covering times for Richardson's model on the \(n\)-cube
• Connections in randomly oriented graphs

Cited In (6)

• A positivity phenomenon in Elser's Gaussian-cluster percolation model
• Correlations for paths in random orientations of \(G(n,p)\) and \(G(n,m)\)
• Connections in randomly oriented graphs
• First critical probability for a problem on random orientations in \(G(n,p)\).
• Percolation clusters as generators for orientation ordering
• Some conditional correlation inequalities for percolation and related processes

This page was built for publication: Positive association of the oriented percolation cluster in randomly oriented graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5222557)