Subcritical SWG(n, c/n): all clusters are small (EPI-6) #
[BCDPTZ22] Lemma C.1 (claim 2 of Theorem 2.1): below the threshold p* = swgThreshold c, every
connected component of the percolated SWG(n, c/n) has O(log n) nodes, w.h.p.
By expect_prob_swg_eq the percolated SWG(n, q) is the percolation of the complete graph with
independent coins, of probability p on the cycle edges and p q = p c / n on the other pairs.
Its clusters are explored breadth-first (Explore), giving every discovered node the weight 1
if it was discovered through a cycle edge and 1 + p₀ otherwise (swgWeight), where
p₀ = p* - ε. A node discovered through a cycle edge has at most one undiscovered cycle
neighbour, any other node at most two, and every node has at most n other undiscovered
neighbours, each reached by a bridge with probability p c / n. With
δ = 1 - p₀ - c p₀ (1 + p₀) > 0 (the subcritical condition, lt_swgThreshold_iff), the expected
weight discovered from a node of weight w is therefore at most (1 - δ / 2) w (swg_step):
this is the two-type Galton–Watson comparison behind the paper's variable
W = Y + ∑_{j ≤ 2Y} L_j, with the weights a left eigenvector of the mean
matrix. The supermartingale tail bound Explore.prob_cluster_gt_le and a union bound over the
n nodes conclude, with β = 64 / δ² and failure probability 2 / n.
The union bound #
Union bound over the components, for any random graph: if the cluster of every vertex
has more than ⌊L⌋₊ vertices with probability at most β, then all components have at most L
vertices with probability at least 1 - n β.
The weights and the one-step bound #
One step of the exploration of the percolated SWG(n, q): if p ≤ p₀, q n = c and
λ dominates the two rows of the mean matrix (p₀ + c p₀ (1 + p₀) ≤ λ for a node discovered
through a cycle edge, 2 p₀ + c p₀ (1 + p₀) ≤ λ (1 + p₀) for the root and a node discovered
through a bridge), then the expected weight discovered from the current node is at most λ
times its weight.
The union-bound arithmetic #
Lemma C.1 #
Lemma C.1 of [BCDPTZ22] with explicit constants: let c > 0, 0 < p₀ < 1 with
δ = 1 - p₀ - c p₀ (1 + p₀) > 0 (that is, p₀ < p*), and n ≥ 2. For q n = c and every
p ≤ p₀, with probability at least 1 - 2 / n over the graph swg n b (b ~ coins q) and the
percolation ω ~ coins p, every connected component of perc (swg n b) ω has at most
(64 / δ²) log n nodes.