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 Gp be a random induced subgraph of G obtained by selecting each vertex of G independently with probability p, <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4g06k" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />0<p<1</alternatives>, and let <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4g031" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Gp≤k</alternatives> be the induced subgraph of Gp obtained by deleting all vertices of Gp with degree greater than k in Gp. We show that if <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4g02h" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />δ≥6</alternatives> and <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4g052" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Δ/δ</alternatives> is not too large then <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4g04j" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Gp≤3</alternatives> almost surely has no infinite component. Moreover, this result is essentially best possible since there are examples where <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4fzxh" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Gp≤k</alternatives> has an infinite component (a) when <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4fzz1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />δ=Δ=3</alternatives>, 4, or 5, and k = 3; (b) when <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4g00g" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Δ≫δ</alternatives> for any δ and k = 3; and (c) when <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4g010" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />δ=Δ</alternatives> for any <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4fwjv" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />δ≥3</alternatives> and <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4fwc8" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />k≥4</alternatives>. In addition, we show that if G is the d‐dimensional lattice <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4fwds" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />ℤd</alternatives> then <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4fwrz" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G1/d≤4</alternatives> almost surely has an infinite component for sufficiently large d. © 2014 Wiley Periodicals, Inc. Random Struct. Alg. 44, 399–418, 2014