Premium
Interference percolation
Author(s) -
Balister Paul,
Bollobás Béla
Publication year - 2014
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20484
Subject(s) - combinatorics , mathematics , degree (music) , vertex (graph theory) , component (thermodynamics) , graph , vertex connectivity , lattice (music) , discrete mathematics , random graph , giant component , connected component , physics , quantum mechanics , acoustics
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