Interference percolation1. Issue 4 (5th March 2013) - Balister, Paul; Bollobás, Béla
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