Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Percolation is independent across edge-disjoint parts

Proved
BunkbedAux.probOf_biUnion_disjoint

by burkh4rt · Sep 12, 2026 · Mathlib 0df444a (Lean v4.33.1)

bunkbedcombinatoricspercolationprobability

Bernoulli bond percolation retains each edge independently, so percolation on a disjoint union of edge sets ought to be the product of the percolations on the pieces. This theorem is that statement, in the combinatorial form in which percolation is defined here.

Let EiE_iEi​, for iii in a finite index type, be pairwise disjoint finite sets of edges, and let www be an arbitrary weight function. For any decidable event E\mathcal{E}E on configurations,

P⋃iEi[E]  =  ∑(Si)(∏iwtEi(Si)) 1[E(⋃iSi)],\mathbb{P}_{\bigcup_i E_i}\bigl[\mathcal{E}\bigr] \;=\; \sum_{(S_i)} \Bigl(\prod_i \mathrm{wt}_{E_i}(S_i)\Bigr)\, \mathbf{1}\Bigl[\mathcal{E}\Bigl(\bigcup_i S_i\Bigr)\Bigr],P⋃i​Ei​​[E]=(Si​)∑​(i∏​wtEi​​(Si​))1[E(i⋃​Si​)],

the sum running over all tuples with Si⊆EiS_i \subseteq E_iSi​⊆Ei​.

The content is twofold. Configurations on the union correspond bijectively to tuples of configurations on the parts, via S↦(S∩Ei)iS \mapsto (S \cap E_i)_iS↦(S∩Ei​)i​ and (Si)i↦⋃iSi(S_i)_i \mapsto \bigcup_i S_i(Si​)i​↦⋃i​Si​ — and it is disjointness that makes this a bijection. And the configuration weight factors, wt⋃Ei(⋃Si)=∏iwtEi(Si)\mathrm{wt}_{\bigcup E_i}\bigl(\bigcup S_i\bigr) = \prod_i \mathrm{wt}_{E_i}(S_i)wt⋃Ei​​(⋃Si​)=∏i​wtEi​​(Si​), because both the product over retained edges and the product over deleted edges split along the partition.

Note that no hypothesis on www is needed: the identity is an algebraic rearrangement, not a probabilistic argument, and holds for arbitrary weights.

Mathematical role. This is the first of the two ingredients needed to analyse a graph built by substituting a gadget for each hyperedge of a hypergraph. The gadget copies are edge-disjoint, so this theorem reduces percolation on the substituted graph to independent percolation within each copy — which is exactly what makes the induced process on the hypergraph a product of per-hyperedge states, i.e. a Wierman--Ziff model. The second ingredient is that connectivity across the union depends only on what each part does to the vertices it shares with the others.

Preamble
import Definitions.Def_BunkbedPercolation
open Bunkbed Finset
Formal statement
namespace BunkbedAux

/-- **Independence across edge-disjoint parts.** If a family of edge sets is pairwise disjoint,
Bernoulli bond percolation on their union is the product of the percolations on the parts: the
probability of any event is a sum over tuples of per-part configurations, weighted by the product
of the per-part weights. -/
theorem probOf_biUnion_disjoint {V : Type*} [Fintype V] [DecidableEq V]
    {ι : Type*} [Fintype ι] [DecidableEq ι] (E : ι → Finset (Sym2 V))
    (hdisj : ∀ i j, i ≠ j → Disjoint (E i) (E j))
    (w : Sym2 V → ℚ) (ev : Finset (Sym2 V) → Prop) [DecidablePred ev] :
    probOf (Finset.univ.biUnion E) w ev
      = ∑ S ∈ Fintype.piFinset (fun i => (E i).powerset),
          (∏ i, weight (E i) w (S i)) *
            (if ev (Finset.univ.biUnion (fun i => S i)) then (1 : ℚ) else 0) := by
  sorry

end BunkbedAux
Source
N. Gladkov, I. Pak, A. Zimin, The bunkbed conjecture is false, PNAS 122 (2025) no. 24, e2420725122, https://doi.org/10.1073/pnas.2420725122, Section 4 (pp. 6-7), where a gadget graph is substituted for each hyperedge.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me