Interference percolation

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 letG p ≤ kbe 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 thenG p ≤ 3almost surely has no infinite component. Moreover, this result is essentially best possible since there are examples whereG p ≤ khas 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ℤ dthenG 1 / d ≤ 4almost surely has an infinite component for sufficiently large d . © 2014 Wiley Periodicals, Inc. Random Struct. Alg. 44, 399–418, 2014