pith. sign in

arxiv: 0811.0949 · v2 · submitted 2008-11-06 · 🧮 math.CO · math.PR

On percolation and the bunkbed conjecture

classification 🧮 math.CO math.PR
keywords conjecturegraphsedgeprobabilitybunkbedcomponenteverypercolation
0
0 comments X
read the original abstract

We study a problem on edge percolation on product graphs $G\times K_2$. Here $G$ is any finite graph and $K_2$ consists of two vertices $\{0,1\}$ connected by an edge. Every edge in $G\times 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,v\in G$. 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.