Subcritical exploration of a percolation cluster (EPI-6) #
The upper bound on cluster sizes of [BCDPTZ22] for SWG(n, c/n) (Lemma C.1) explores the
cluster of a node s in the percolation graph perc G ω breadth-first, with deferred decisions on
the edge coins. Here the coins are independent Bernoulli(r e) with possibly different
probabilities, and the search processes one node per step: it reads at once the block of all
pairs from the current node to its undiscovered G-neighbours, and appends the open ones to the
queue.
Every discovered node y ≠ s carries the weight h e of the pair e through which it was
discovered (the root carries w₀). If the expected weight discovered from a node of weight w
is at most λ w (hypothesis hstep, with κ λ ≤ 1, the subcritical condition), the potential
exp θ (discovered weight − κ λ · processed weight) is a supermartingale (the core's
Distribution.expect_prod_hist_le_one_of_fresh); a cluster with more than t nodes forces t
processed nodes and a large potential, whence, by Markov's inequality (prob_cluster_gt_le),
P(|C(s)| ≥ t + 1) ≤ exp (-θ ((1 - κ λ) t w_min - w_max)).
For SWG(n, c/n) the weights distinguish nodes reached through a cycle edge from nodes reached
through a bridge, the two types behind the paper's Galton–Watson comparison (Appendix C).
The undiscovered G-neighbours of v.
Equations
- Epidemics.Explore.fresh G σ v = {y : V | y ∉ σ.order ∧ G.Adj v y}
Instances For
The block of pairs read when processing the current node σ.order[σ.proc] (empty when the
search is over).
Equations
Instances For
The nodes discovered from v when the open pairs are A.
Equations
- Epidemics.Explore.newV G σ v A = {y ∈ Epidemics.Explore.fresh G σ v | s(v, y) ∈ A}
Instances For
One step of the search, given the set A of open pairs of the block.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The state after the observations l, starting from the root s of weight w₀.
Equations
- Epidemics.Explore.state G h s w₀ l = List.foldl (Epidemics.Explore.update G h) { order := [s], proc := 0, wt := fun (x : V) => w₀ } l
Instances For
Invariants #
The invariants of the search.
Instances For
The order only grows, and proc only grows.
proc counts the steps until the search is over.
Freshness of the blocks #
Every pair read along the history l has a processed endpoint.
The search on the actual coins #
The observation process of the search on the coins ω: the open pairs of each block.
Equations
- Epidemics.Explore.obs s w₀ l ω = {e ∈ Epidemics.Explore.block G (Epidemics.Explore.state G h s w₀ l) | ω e = true}
Instances For
After processing a node, all its open neighbours are discovered.
The potential and the supermartingale #
The potential of the search: discovered weight (root excluded) minus c times the weight of
the processed nodes.
Equations
Instances For
The factor of the supermartingale after the history l, when the open pairs of the block
are A.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The open pairs of the block are the pairs to the newly discovered nodes.
Along the search on the coins ω, the product of the factors is exp (θ · potential).
The weights of the discovered nodes lie in [wmin, wmax].
Lower bound on the potential when t nodes are processed and t + 1 discovered.
The tail bound #
When the search is over (every discovered node processed), the discovered nodes contain the cluster of the root.
A cluster with more than t nodes forces t processed and t + 1 discovered nodes after
t steps.
One step of the supermartingale: the factor has expectation at most 1.
Tail of the cluster size (subcritical exploration with weights): with independent
Bernoulli(r e) coins, weights h e ∈ [wmin, wmax], root weight w₀ ∈ [wmin, wmax], and
expected weight discovered from every node of weight w at most λ w (hstep), the cluster of
s has more than t nodes with probability at most
exp (-θ ((1 - κ λ) t wmin - wmax)), for every θ ≥ 0 and κ ≤ 2 with θ wmax ≤ κ - 1.