On Percolation and the Bunkbed Conjecture

DOI10.1017/S0963548309990666zbMATH Open1298.05278arXiv0811.0949OpenAlexW2068525708WikidataQ123334337 ScholiaQ123334337MaRDI QIDQ3068816FDOQ3068816

Svante Linusson

Publication date: 17 January 2011

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

Abstract: We study a problem on edge percolation on product graphs $Gimes{K}_2$. Here $G$ is any finite graph and $K_2$ consists of two vertices $0,1$ connected by an edge. Every edge in $Gimes{K}_2$ is present with probability $p$ independent of other edges. The Bunkbed conjecture states that for all $G$ and $p$ the probability that $(u,0)$ is in the same component as $(v,0)$ is greater than or equal to the probability that $(u,0)$ is in the same component as $(v,1)$ for every pair of vertices $u,vinG$. We generalize this conjecture and formulate and prove similar statements for randomly directed graphs. The methods lead to a proof of the original conjecture for special classes of graphs $G$, in particular outerplanar graphs.

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

zbMATH Keywords

edge percolation on product graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Percolation
• Random walks and electrical resistances in products of graphs
• The transitive closure of a random digraph
• General percolation and random graphs
• Some conditional correlation inequalities for percolation and related processes
• A correlation inequality for connection events in percolation
• On a Conjecture of Bollobás and Brightwell Concerning Random Walks on Product Graphs
• Infinite paths in randomly oriented lattices

Cited In (5)

• Correlations for paths in random orientations of G(n,p) and G(n,m)
• Erratum to ‘On Percolation and the Bunkbed Conjecture’
• The bunkbed conjecture on the complete graph
• A new proof of the bunkbed conjecture in the \(p \uparrow 1\) limit
• The bunkbed conjecture holds in the limit

This page was built for publication: On Percolation and the Bunkbed Conjecture

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