Abstract:

At the Lars Holst symposium last year Olle Häggström discussed percolation on product graphs $G\times P_1$. Here $G$ is any graph and $P_1$ consists of two vertices connected by an edge. In edge percolation every edge in $G\times P_1$ is present independently with probability $p$. Olle stated a conjecture that for all $G$ and $p$ the probability that $(u,x)$ is in the same component as $(v,x)$ is greater than the probability that $(u,x)$ is in the same component as $(v,y)$ for every pair of vertices $u,v\in G$.

This innocent looking conjecture seems strangely difficult to prove. I will discuss a number of possible ways to attack this problem, and will prove it for special classes of graphs $G$. Along the way I will present several related conjectures, prove their relations and discuss why they seem difficult to prove.