Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-29T17:31:12.362Z Has data issue: false hasContentIssue false
  • English
  • Français

On Percolation and the Bunkbed Conjecture

Published online by Cambridge University Press:  17 February 2010

SVANTE LINUSSON
SVANTE LINUSSON*
Affiliation:
Department of Mathematics, KTH-Royal Institute of Technology, SE-100 44, Stockholm, Sweden (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 1 , January 2011 , pp. 103 - 117
Copyright
Copyright © Cambridge University Press 2010

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

[1]Alm, S. E. and Linusson, S. (2009) A counter-intuitive correlation in a random tournament. Combin. Probab. Comput., to appear. arXiv:0906.0240Google Scholar
[2]Alm, S. E. and Linusson, S. (2009) Correlations for paths in random orientations of G(n, p). Preprint. arXiv:0906.0720Google Scholar
[3]van den Berg, J. and Kahn, J. (2001) A correlation inequality for connection events in percolation. Ann. Probab. 29 123–126.Google Scholar
[4]van den Berg, J., Häggström, O. and Kahn, J. (2006) Some conditional correlation inequalities for percolation and related processes. Random Struct. Alg. 29 417–435.CrossRefGoogle Scholar
[5]Bollobás, B. and Brightwell, G. (1997) Random walks and electrical resistances in products of graphs. Discrete Appl. Math. 73 69–79.CrossRefGoogle Scholar
[6]Grimmett, G. R. (1999) Percolation, Springer, Berlin.CrossRefGoogle Scholar
[7]Grimmett, G. R. (2001) Infinite paths in randomly oriented lattices. Random Struct. Alg. 18 257–266.CrossRefGoogle Scholar
[8]Häggström, O. (1998) On a conjecture of Bollobás and Brightwell concerning random walks on product graphs. Combin. Probab. Comput. 7 397–401.CrossRefGoogle Scholar
[9]Häggström, O. (2003) Probability on Bunkbed Graphs. In Proc. FPSAC'03: Formal Power Series and Algebraic Combinatorics (Linköping, Sweden). Available at http://www.fpsac.org/FPSAC03/ARTICLES/42.pdfGoogle Scholar
[10]Harris, T. E. (1960) A lower bound for the critical probability in a certain percolation process. Proc. Cambridge Philos. Soc. 56 13–20.CrossRefGoogle Scholar
[11]Karp, R. M. (1990) The transitive closure of a random digraph. Random Struct. Alg. 1, 73–93.CrossRefGoogle Scholar
[12]Linusson, S. (2009) A note on correlations in randomly oriented graphs. Preprint. arXiv:0905.2881Google Scholar
[13]McDiarmid, C. (1981) General percolation and random graphs. Adv. Appl. Probab. 13 40–60.CrossRefGoogle Scholar