OctoInformBeta

OpenAI preprint, September 2026 · §2. A finite connection comparison

Corollary 2.3: Comparisons for hyperedges and for bond and site percolation in finite lattice subgraphs

A bound for failed target connections.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

A connection from an origin to an intermediate set can stop short of a target. Corollary 2.3 compares the probability of this event with target connection probabilities from the vertices of the intermediate set.

A labelled hypergraph H=(He)e∈EH=(H_e)_{e\in E} on a vertex set VV is a family of subsets He⊆VH_e\subseteq V , indexed by a set EE of hyperedge labels; empty hyperedges are permitted.✦ A hyperedge configuration ω∈{0,1}E\omega\in\{0,1\}^E is an assignment of an open state 11 or a closed state 00 to each hyperedge label. For a labelled hypergraph HH on VV , a configuration ω\omega , and a forbidden set D⊆VD\subseteq V , open hyperedge adjacency x∼H,ω,Dyx\sim_{H,\omega,D}y is the relation between vertices x,y∈Vx,y\in V that holds when they lie in a common open hyperedge disjoint from DD , as in (1): x∼H,ω,Dy⇔∃e∈E:ωe=1,He∩D=⌀,x,y∈He.x\sim_{H,\omega,D}y \quad\Longleftrightarrow\quad \exists e\in E:\ \omega_e=1,\quad H_e\cap D=\varnothing, \quad x,y\in H_e.(1)✦ Open hyperedge connectivity x↔H,Dyx\leftrightarrow_{H,D}y in a labelled hypergraph HH on VV , with forbidden set D⊆VD\subseteq V , is the relation between vertices x,y∈Vx,y\in V that holds when a finite chain of open hyperedge adjacencies avoiding DD joins xx to yy ; a chain of length zero is allowed.✦ A connection {x↔H,DS}\{x\leftrightarrow_{H,D}S\} from a vertex x∈Vx\in V to a target set S⊆VS\subseteq V in the labelled hypergraph HH , with forbidden set DD , is the event that xx is connected to some vertex of SS by open hyperedges avoiding DD , as in (2): {x↔H,DS}={ω:∃y∈S,x↔H,Dy}.\{x\leftrightarrow_{H,D}S\} =\{\omega:\exists y\in S,\ x\leftrightarrow_{H,D}y\}.(2)✦

The Bernoulli product law μp\mu_p on hyperedge configurations {0,1}E\{0,1\}^E is the probability measure under which the hyperedge labels have independent open states with probabilities pe∈[0,1]p_e\in[0,1] .✦ For an event FF of hyperedge configurations, its real probability ℙp(F)\mathbb P_p(F) under the Bernoulli product law μp\mu_p is the integral of its indicator, as in (3): μp=⨂e∈EBernoulli⁡(pe),ℙp(F)=∫𝟏F(ω)dμp(ω).\mu_p=\bigotimes_{e\in E}\operatorname{Bernoulli}(p_e), \qquad \mathbb P_p(F)=\int\mathbf 1_F(\omega)\,d\mu_p(\omega).(3) For site percolation the labels are vertices, with independent open probabilities px∈[0,1]p_x\in[0,1] .

Open site adjacency x∼K,ωsiteyx\sim^{\mathrm{site}}_{K,\omega}y in a simple graph KK on VV and a configuration ω∈{0,1}V\omega\in\{0,1\}^V is the relation between vertices x,y∈Vx,y\in V that holds when they are adjacent in KK and both open, as in (4): x∼K,ωsitey⇔x∼Ky and ωx=ωy=1.x\sim^{\mathrm{site}}_{K,\omega}y \quad\Longleftrightarrow\quad x\sim_K y\ \text{ and }\ \omega_x=\omega_y=1.(4)✦ Open site connectivity x↔Ksiteyx\leftrightarrow^{\mathrm{site}}_K y in a simple graph KK is the relation between vertices x,yx,y of KK that holds when a finite path of open vertices in KK joins xx to yy .✦ A path of length zero requires its vertex to be open. A site connection {x↔KsiteS}\{x\leftrightarrow^{\mathrm{site}}_K S\} from a vertex xx of a simple graph KK on VV to a set S⊆VS\subseteq V is the event that an open site path in KK joins xx to some vertex of SS , as in (5): {x↔KsiteS}={ω:∃y∈S,x↔Ksitey}.\{x\leftrightarrow^{\mathrm{site}}_K S\} =\{\omega:\exists y\in S,\ x\leftrightarrow^{\mathrm{site}}_K y\}.(5)✦

Finite Lattice Subgraphs

The cubic lattice has vertex set ℤ3\mathbb Z^3 .✦ For a coordinate direction i∈{0,1,2}i\in\{0,1,2\} , let 𝒆i\mathbf e_i be the corresponding unit vector; for a vertex x∈ℤ3x\in\mathbb Z^3, the positive coordinate step from xx is x+𝒆ix+\mathbf e_i .✦ A lattice bond (x,i)(x,i) is a pair consisting of a vertex x∈ℤ3x\in\mathbb Z^3 and a coordinate direction i∈{0,1,2}i\in\{0,1,2\} , joining xx to x+𝒆ix+\mathbf e_i .✦ The bond space ℬ\mathcal B is the set of lattice bonds, and the endpoint set ∂e\partial e of a bond ee is the set of its two endpoints, as in (6); endpoint incidence is the relation that holds when two vertices are the endpoints of a bond in either order. ℬ=ℤ3×{0,1,2},∂(x,i)={x,x+𝒆i}.\mathcal B=\mathbb Z^3\times\{0,1,2\}, \qquad \partial(x,i)=\{x,x+\mathbf e_i\}.(6) A finite lattice subgraph G=(VG,EG)G=(V_G,E_G) consists of finite sets VG⊆ℤ3V_G\subseteq\mathbb Z^3 and EG⊆ℬE_G\subseteq\mathcal B such that ∂e⊆VG\partial e\subseteq V_G for every e∈EGe\in E_G .✦ Its vertices are the elements of VGV_G .✦ The underlying simple graph of a finite lattice subgraph G=(VG,EG)G=(V_G,E_G) is the graph on VGV_G in which two vertices are adjacent when a bond of EGE_G has those endpoints.✦

A lattice bond configuration ω∈{0,1}ℬ\omega\in\{0,1\}^{\mathcal B} is an assignment of a state to every lattice bond.✦ Open bond adjacency in a finite lattice subgraph G=(VG,EG)G=(V_G,E_G) is the relation between vertices of VGV_G that holds when they are the endpoints of an open bond of EGE_G .✦ Bond connectivity x↔Gbondyx\leftrightarrow^{\mathrm{bond}}_G y in a finite lattice subgraph G=(VG,EG)G=(V_G,E_G) is the relation between vertices x,y∈VGx,y\in V_G that holds when a finite chain of open bond adjacencies in GG joins them, allowing a chain of length zero.✦ A lattice site configuration ω∈{0,1}ℤ3\omega\in\{0,1\}^{\mathbb Z^3} is an assignment of a state to every lattice vertex.✦ Site connectivity x↔Gsiteyx\leftrightarrow^{\mathrm{site}}_G y in a finite lattice subgraph G=(VG,EG)G=(V_G,E_G) is the relation between vertices x,y∈VGx,y\in V_G that holds when an open site path in the underlying simple graph of GG joins them.✦

For either kind q∈{bond,site}q\in\{\mathrm{bond},\mathrm{site}\} , a connection {x↔GqS}\{x\leftrightarrow^q_G S\} from a vertex x∈VGx\in V_G of a finite lattice subgraph G=(VG,EG)G=(V_G,E_G) to a set S⊆ℤ3S\subseteq\mathbb Z^3 is the event that xx is connected in GG to some vertex of S∩VGS\cap V_G , as in (7): {x↔GqS}={ω:∃y∈S∩VG,x↔Gqy}.\{x\leftrightarrow^q_G S\} =\{\omega:\exists y\in S\cap V_G,\ x\leftrightarrow^q_G y\}.(7) The lattice laws ℙp\mathbb P_p are independent Bernoulli product measures over all bonds or all vertices of ℤ3\mathbb Z^3 , with the corresponding individual probabilities in [0,1][0,1] .✦

The Claim

Theorem 1. Let HH be a labelled hypergraph on a finite vertex set VV, with independent hyperedge probabilities pe∈[0,1]p_e\in[0,1], an origin o∈Vo\in V, and sets A,T⊆VA,T\subseteq V. Suppose b∈ℝb\in\mathbb R satisfies ℙp(a↔H,⌀T)≥1−b\mathbb P_p(a\leftrightarrow_{H,\varnothing}T)\ge1-b for every a∈Aa\in A. Then ℙp(o↔H,⌀A,o↮H,⌀T)≤bℙp(o↔H,⌀A).\mathbb P_p\bigl(o\leftrightarrow_{H,\varnothing}A,\ o\not\leftrightarrow_{H,\varnothing}T\bigr) \le b\,\mathbb P_p(o\leftrightarrow_{H,\varnothing}A).(8)✦ If also b≥0b\ge0, then ℙp(o↔H,⌀A,o↮H,⌀T)≤b.\mathbb P_p\bigl(o\leftrightarrow_{H,\varnothing}A,\ o\not\leftrightarrow_{H,\varnothing}T\bigr)\le b.(9)✦

Let KK be a simple graph on a finite vertex set VV, with independent site probabilities px∈[0,1]p_x\in[0,1], an origin o∈Vo\in V, and sets A,T⊆VA,T\subseteq V. Suppose b≥0b\ge0 and ℙp(a↔KsiteT)≥1−b\mathbb P_p(a\leftrightarrow^{\mathrm{site}}_K T)\ge1-b for every a∈Aa\in A. Then ℙp(o↔KsiteA,o↮KsiteT)≤b.\mathbb P_p\bigl(o\leftrightarrow^{\mathrm{site}}_K A,\ o\not\leftrightarrow^{\mathrm{site}}_K T\bigr)\le b.(10)✦

Let G=(VG,EG)G=(V_G,E_G) be a finite lattice subgraph, let o∈VGo\in V_G and A,T⊆ℤ3A,T\subseteq\mathbb Z^3, and let b≥0b\ge0. Under the lattice bond law with probabilities pe∈[0,1]p_e\in[0,1], suppose ℙp(a↔GbondT)≥1−b\mathbb P_p(a\leftrightarrow^{\mathrm{bond}}_G T)\ge1-b for every a∈A∩VGa\in A\cap V_G. Then ℙp(o↔GbondA,o↮GbondT)≤b.\mathbb P_p\bigl(o\leftrightarrow^{\mathrm{bond}}_G A,\ o\not\leftrightarrow^{\mathrm{bond}}_G T\bigr)\le b.(11)✦ Under the lattice site law with probabilities px∈[0,1]p_x\in[0,1], suppose ℙp(a↔GsiteT)≥1−b\mathbb P_p(a\leftrightarrow^{\mathrm{site}}_G T)\ge1-b for every a∈A∩VGa\in A\cap V_G. Then ℙp(o↔GsiteA,o↮GsiteT)≤b.\mathbb P_p\bigl(o\leftrightarrow^{\mathrm{site}}_G A,\ o\not\leftrightarrow^{\mathrm{site}}_G T\bigr)\le b.(12)✦

In the paper, the result reads: for independent bond or site percolation on a finite undirected graph, with arbitrary individual probabilities in [0,1][0,1], an origin oo, vertex sets A,TA,T, and b∈[0,1]b\in[0,1], the assumptions ℙp(a↔T)≥1−b\mathbb P_p(a\leftrightarrow T)\ge1-b for every a∈Aa\in A imply ℙp(o↔A,o↮T)≤b\mathbb P_p(o\leftrightarrow A,\ o\not\leftrightarrow T)\le b, where ↔\leftrightarrow denotes connection in the chosen model, also after any deterministic collection of bits is fixed.

What Is Checked

The comparisons (8) and (9) are stated over finite vertex hypergraphs with independent hyperedge bits, (10) over finite simple graphs with independent site bits, and (11) and (12) over finite lattice subgraphs under the full lattice bond and site product laws, respectively.