Interference percolation1. Issue 4 (5th March 2013)

• Record Type: Journal Article
• Authors: Balister, Paul; Bollobás, Béla
• Is Part Of: Random structures & algorithms. Volume 44:Issue 4(2014)
• Page Start: 399
• Page End: 418
• Publication Date: 2013-03-05
• Subjects: percolation -- graph theory; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20484
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Let G be an infinite connected graph with minimum degree δ and maximum degree Δ. Let G p be a random induced subgraph of G obtained by selecting each vertex of G independently with probability p, 0 < p < 1, and let G p ≤ k be the induced subgraph of G p obtained by deleting all vertices of G p with degree greater than k in G p . We show that if δ ≥ 6 and Δ / δ is not too large then G p ≤ 3 almost surely has no infinite component. Moreover, this result is essentially best possible since there are examples where G p ≤ k has an infinite component (a) when δ = Δ = 3, 4, or 5, and k = 3; (b) when Δ ≫ δ for any δ and k = 3; and (c) when δ = Δ for any δ ≥ 3 and k ≥ 4 . In addition, we show that if G is the d ‐dimensional lattice ℤ d then G 1 / d ≤ 4 almost surely has an infinite component for sufficiently large d . © 2014 Wiley Periodicals, Inc. Random Struct. Alg. 44, 399–418, 2014