Components, large and small, are as they should be I: Supercritical percolation on regular graphs of growing degree

We provide sufficient conditions for a regular graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of growing degree <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d"> <mml:semantics> <mml:mi>d</mml:mi> <mml:annotation encoding="application/x-tex">d</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , guaranteeing a phase transition in its random subgraph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G Subscript p"> <mml:semantics> <mml:msub> <mml:mi>G</mml:mi> <mml:mi>p</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">G_p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> similar to that of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G left-parenthesis n comma p right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>p</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">G(n,p)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> when <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p dot d almost-equals 1"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo> ⋅ </mml:mo> <mml:mi>d</mml:mi> <mml:mo> ≈ </mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">p\cdot d\approx 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . These conditions capture several well-studied graphs, such as (percolation on) the complete graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K Subscript n"> <mml:semantics> <mml:msub> <mml:mi>K</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">K_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , the binary hypercube <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper Q Superscript d"> <mml:semantics> <mml:msup> <mml:mi>Q</mml:mi> <mml:mi>d</mml:mi> </mml:msup> <mml:annotation encoding="application/x-tex">Q^d</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d"> <mml:semantics> <mml:mi>d</mml:mi> <mml:annotation encoding="application/x-tex">d</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -regular expanders, and random <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d"> <mml:semantics> <mml:mi>d</mml:mi> <mml:annotation encoding="application/x-tex">d</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -regular graphs. In particular, this serves as a unified proof for these (and other) cases. Suppose that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d"> <mml:semantics> <mml:mi>d</mml:mi> <mml:annotation encoding="application/x-tex">d</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -regular graph on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> vertices, with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d equals omega left-parenthesis 1 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>=</mml:mo> <mml:mi> ω </mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">d=\omega (1)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="epsilon greater-than 0"> <mml:semantics> <mml:mrow> <mml:mi> ϵ </mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">\epsilon &gt;0</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be a small constant, and let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p equals StartFraction 1 plus epsilon Over d EndFraction"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>=</mml:mo> <mml:mfrac> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi> ϵ </mml:mi> </mml:mrow> <mml:mi>