Because \(G\) is vertex-transitive, the distribution of \(\alpha ^*_i\) is the same for every \(i\), so \(\mathbb {E}[\alpha ^*]\) is a multiple of \(\mathbb {1}\). By Corollary 37, with probability at least \(1 - \tfrac {6}{n}\) at least \((1-t)n\) vertices lie in non-bipartite components, where \(t\) is as above; by Lemma 24 those vertices have \(\alpha ^*_i = 1\).

First statement. Since \(\alpha ^*_i \ge 0\),

Second statement. Using \(|1 - \alpha ^*_i| \le 1\) always,

Third statement. This is Lemma 28.

Bound the operator norm by the sum of absolute entries of a row:

For \(S \subset V\) let \(E_S\) be the event that \(S\) is exactly a connected component of \(G(p)\), let \(\mathcal{E}(i) = \{ E_S : i \in S\} \), and for \(E \in \mathcal{E}(i)\) let \(\alpha _i(E)\) be the value of \(\alpha _i\) conditioned on \(E\). Since \(1 - \alpha _i\) is determined by which component contains \(i\) and whether it is bipartite,

where the second line uses \(|1-\alpha _i| \le 1\). Note \(\Pr [E_S]\Pr [E_T] {\gt} \Pr [E_S \cap E_T]\) exactly when the two events are incompatible, i.e. \(S \neq T\) and \(S \cap T \neq \emptyset \); define \(I(S,T) = 1\) in that case and \(0\) otherwise.

Using vertex transitivity, for a fixed \(i\) with \(|S| \le k\) one rewrites, with \(A_j \subset \operatorname {Aut}(G)\) the automorphisms sending \(j \mapsto 1\) and using \(\Pr [E_T] = \Pr [E_{\sigma (T)}]\),

Bounding \(I(S,\sigma (T)) \le \mathbf{1}[S \cap \sigma (T) \neq \emptyset ]\) and using that \(\sigma (u)\) is uniform on \(V\) (vertex transitivity), so \(\mathbb {E}_{\sigma }[|S \cap \sigma (T)|] = \tfrac {|S||T|}{n}\), gives

the last step using Corollary 37 (a vertex is in a giant component of size \({\gt} n/2\) with probability \(\ge 1 - t - \tfrac {6}{n}\)). Summing over all \(j\), splitting into pairs with \(\max (|S|,|T|) \le k\) and \(\max (|S|,|T|) {\gt} k\), and applying Claim 35 for the large pairs,

Consider the growing process of Algorithm 30 (a generalization of the standard component-exploration process), started from a vertex set \(V_0\): it reveals edges of \(G\) one at a time, including an edge in \(G(p)\) with probability \(1-p\) (variable \(X_t\)), maintaining the explored vertices \(V_t\), the explored \(G(p)\)-edges \(S_t\), the explored non-\(G(p)\) edges \(B_t\), and the frontier \(F_t = \partial (V_t)\setminus B_t\) of unexplored edges. Since the explored \(G(p)\)-edges form a forest, \(|V_t| = |V_0| + |S_t|\) and \(|B_t| = t - |S_t|\). Claim 31 lower bounds the frontier size, and Claim 32 shows every vertex is in a component of size \(\le k\) or \({\gt} n/2\) with probability \(1 - \tfrac {4}{n}\). Since there is at most one component of size \({\gt} n/2\), all such vertices lie in one giant component. Claim 33 bounds the number of vertices in small components, yielding the giant-component size bound and the failure probability \(1 - \tfrac {5}{n}\).

By the Expander Mixing Lemma (Lemma 9) applied to \(V_t\) and its complement, \(|\partial (V_t)| \ge \lambda |V_t|\big(1 - \tfrac {|V_t|}{n}\big) \ge \alpha _t|V_t|\). Hence, using \(|F_t| = |\partial (V_t)\setminus B_t| \ge \alpha _t|V_t| - |B_t|\), \(|V_t| = |S_t| + |V_0|\) and \(|B_t| = t - |S_t|\),

since \(|S_t| = \sum _{i=1}^t X_i\).

Conditioned on \(v\) in a component of size \(\ge k\), the growing process on \(\{ v\} \) takes at least \(k(1+\alpha _k)\) steps. By the third assumption, \(k \le \tfrac {n}{(3+\epsilon )\log n}\), so \(\alpha _t \le \tfrac 12\) for the relevant \(t\). Using the frontier bound (Lemma 31) the component stays \(\le n/2\) only if the random walk \(\sum _{i=1}^t(X_i(\alpha _t+1)-1)\) becomes nonpositive, so

By the Chernoff bound (Lemma 4) for Bernoulli\((1-p)\) variables,

Summing the geometric series and using the second assumption and the definition of \(k\) bounds the total by \(\dfrac {\exp (-k\epsilon ^2/(2(1+\epsilon )))}{\frac{1-p}{4}(1-\frac{1}{1+\epsilon })^2} = \tfrac {4}{n^2}\). A union bound over the \(n\) vertices gives the claim.

By Claim 35, the first \(\log (n)\) moments of \(Y\) are upper bounded by those of \(\mathrm{Binomial}(n,q)\) with \(q = \tfrac {p^{\lambda (1-\frac{1}{3+\epsilon })}}{(1-p)^2}\). By Proposition 36 and Markov’s inequality (Lemma 2) applied to the \(\log (n)\)-th centralized moment,

For \(\beta \) let \(d_\beta (\alpha )\) be the extinction probability of \(S^{(\beta )}(\alpha )\). We compare \(S^{(\beta )}(\alpha )\) with the integer walk \(S(\lfloor \alpha \rfloor )\): \(d_\beta (\alpha ) \le d_{\lceil \beta \rceil }(\lfloor \alpha \rfloor ) = d_1(\lfloor \alpha \rfloor )^{\lceil \beta \rceil }\), and a first-step analysis gives \(d_1(\lfloor \alpha \rfloor ) = p + (1-p)d_1(\lfloor \alpha \rfloor )^{\lfloor \alpha \rfloor +1}\), whence \(d_1(\lfloor \alpha \rfloor ) \le \tfrac {p}{(1-p)^{1/\lfloor \alpha \rfloor }}\). Therefore for any positive integer \(c\),

We have \(\Pr [\max _{v\in S}|C_v| \le k] \le \Pr [|\bigcup _{v\in S}C_v| \le ck]\). This is the probability that the growing process started at \(V_0 = S\) terminates before reaching size \(ck\). From \(k \le n(1 - \tfrac {1}{3+\epsilon })\) (for \(c \le \log n\)), the process terminates early only if the random walk \(\sum _{i=1}^{\infty }\big(X_i(\lambda (1-\tfrac 1{3+\epsilon })+1) - 1\big) + c\lambda (1-\tfrac 1{3+\epsilon })\) becomes extinct. Since \(\lambda (1-\tfrac 1{3+\epsilon }) {\gt} 1\) by the first assumption, Lemma 34 (with \(\alpha = \lambda (1-\tfrac 1{3+\epsilon })\), \(\beta = c\alpha \)) gives the stated bound.

Let \(X_i, Y_i\) be i.i.d. Bernoulli\((q)\). By Jensen’s inequality (Lemma 3) applied to the convex map \(x \mapsto x^c\),

Write \(X_i - Y_i = r_i Z_i\) with \(r_i\) i.i.d. Rademacher and \(Z_i \sim \mathrm{Bernoulli}(2q(1-q))\). Since even moments of a standard Gaussian \(g_i\) dominate those of a Rademacher and odd moments vanish for both, \(\mathbb {E}[(\sum _i r_i Z_i)^c] \le \mathbb {E}[(\sum _i g_i Z_i)^c]\). As \(\mathbb {E}[Z_i^k] = 2q(1-q)\) for all \(k \ge 1\), comparing moments gives \(\sum _i g_i Z_i \sim 2q(1-q)\sum _i g_i \sim 2q(1-q)\mathcal{N}(0,n)\), so

where the first inequality uses Stirling (Lemma 5).

Use “edge sprinkling”: let \(q = pe^{1/\lambda }\). Create \(G(p)\) in two steps: Step 1 forms \(G(q)\) by deleting edges with probability \(q\); Step 2 adds back each absent edge of \(G\) with probability \(1 - \tfrac {p}{q}\). By Theorem 29 applied with \(q\), with probability \(\ge 1 - \tfrac 5n\) the graph \(G(q)\) has a giant component \(C\) of size \(n(1-s)\), \(s = \tfrac {e^2 p^{\lambda (1-\frac1{3+\epsilon })}}{(1-pe^{1/\lambda })^2}\). If \(C\) were bipartite with sides \(L \supseteq R\), \(r = |R|/n \ge \tfrac {1-s}{2}\), then by the Expander Mixing Lemma (Lemma 9) there are at least \(n(dr^2 - (d-\lambda )r(1-r))\) edges of \(G\) inside \(R\); assumption (3) makes this \(\ge \tfrac {n\epsilon }{4}\). The probability Step 2 adds no edge inside \(R\) is at most \((p/q)^{n\epsilon /4} \le \exp (-\tfrac {n\epsilon }{4\lambda }) \le \tfrac 1n\). Hence with probability \(\ge 1 - \tfrac 5n - \tfrac 1n\) there is a non-bipartite giant component, and the second statement follows from Theorem 29.