OctoInformBeta

OpenAI preprint, September 2026 · §4. Counting equivalence and homogeneity · §4

The giant component: Deleting at most 6M6M edges from the cubic grid of side LL leaves a component of more than L3/2L^3/2 vertices, under an explicit bound

Deleting few grid edges leaves a giant component.

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

For a natural number nn, the cubic grid ΓL\Gamma_L of side L=n+1L = n + 1 has as vertices the integer triples V={0,…,L−1}3,|V|=L3,V = \{0, \dots, L-1\}^3, \qquad |V| = L^3,(1) and the structures AbA_b of the separation of choiceless polynomial time with counting from polynomial time, one for each charge b∈𝔽3Vb \in \mathbb{F}_3^V (a function from VV to 𝔽3\mathbb{F}_3), are built on ΓL\Gamma_L.

The edges of ΓL\Gamma_L are the unit segments parallel to the coordinate axes, each given by its lower endpoint: E=Ex⊔Ey⊔Ez,Ex={0,…,L−2}×{0,…,L−1}2,E = E_x \sqcup E_y \sqcup E_z, \qquad E_x = \{0, \dots, L-2\} \times \{0, \dots, L-1\}^2,(2)✦ with EyE_y and EzE_z the same products with the short range {0,…,L−2}\{0, \dots, L-2\} in the second and in the third place. The edge e∈Exe \in E_x given by (i,j,k)(i,j,k) runs from its tail e−=(i,j,k)e^- = (i,j,k) to its head e+=(i+1,j,k)e^+ = (i+1,j,k); the edges of EyE_y and EzE_z given by (i,j,k)(i,j,k) run from (i,j,k)(i,j,k) to (i,j+1,k)(i,j+1,k) and to (i,j,k+1)(i,j,k+1).

Delete a set T⊆ET \subseteq E of edges from ΓL\Gamma_L. The question is whether, for |T||T| small against L3L^3, the remaining graph ΓL−T\Gamma_L - T keeps a connected component with more than half of the vertices, a giant component, and how that component changes as more edges are deleted.

Components and Giant Components

Let Γ\Gamma be a finite directed multigraph: a finite set VV of vertices, a finite set EE of edges, and for each edge ee a tail e−e^- and a head e+e^+ in VV. The grid ΓL\Gamma_L is one, with the tails and heads above.

For a set T⊆ET \subseteq E, the edge relation of Γ−T\Gamma - T is the binary relation →T\to_T on VV given by x→Ty⇔there is an edge e∈E\T with e−=x and e+=y.x \to_T y \iff \text{there is an edge } e \in E \setminus T \text{ with } e^- = x \text{ and } e^+ = y.(3)✦ Connectivity in Γ−T\Gamma - T is the smallest equivalence relation ∼T\sim_T on VV containing →T\to_T.✦ A connected component of Γ−T\Gamma - T is an equivalence class of ∼T\sim_T✦, and the component of a vertex vv is the class containing it: CT(v)={w∈V:v∼Tw}.C_T(v) = \{ w \in V : v \sim_T w \}.(4)✦ A vertex vv of Γ\Gamma lies in a giant component of Γ−T\Gamma - T when its component holds more than half of the vertices: |V|<2|CT(v)|.|V| < 2\,|C_T(v)|.(5)✦

The Size Condition

The box isoperimetric constant is the real number c=1−2−1/3≈0.206.c = 1 - 2^{-1/3} \approx 0.206.(6)✦ A pair (n,M)(n, M) of natural numbers satisfies the giant size bound when, with L=n+1L = n + 1, (12Mc)3/2<L3.\Bigl( \frac{12M}{c} \Bigr)^{3/2} < L^3.(7)

The Claim

Theorem 1. Let L=n+1L = n + 1 and let TT be a set of edges of the cubic grid ΓL\Gamma_L.

  1. If SS is a set of connected components of ΓL−T\Gamma_L - T, each with at most L3/2L^3/2 vertices, then ∑C∈S|C|≤(2|T|c)3/2.\sum_{C \in S} |C| \le \Bigl( \frac{2|T|}{c} \Bigr)^{3/2}.(8)✦

  2. If (2|T|/c)3/2<L3(2|T|/c)^{3/2} < L^3, then ΓL−T\Gamma_L - T has a connected component CC with L3<2|C|.L^3 < 2\,|C|.(9)✦

  3. If nn and MM satisfy the giant size bound (7) and |T|≤6M|T| \le 6M, then there is a vertex vv of ΓL\Gamma_L with L3<2|CT(v)|.L^3 < 2\,|C_T(v)|.(10)✦

  4. In any finite directed multigraph Γ\Gamma with vertex set VV, if T⊆UT \subseteq U are sets of edges and vv is a vertex with |V|<2|CU(v)||V| < 2\,|C_U(v)|, then |V|<2|CT(v)|.|V| < 2\,|C_T(v)|.(11)✦

In the paper, the result reads: for LL large and a set TT of at most 6M6M deleted edges, a unique component of ΓL−T\Gamma_L - T has more than L3/2L^3/2 vertices, and it shrinks monotonically as more edges are deleted.

The giant size bound (7) takes the place of the paper’s choice M=⌊L7/4⌋M = \lfloor L^{7/4} \rfloor with LL large.

What Is Checked

The claim is stated over the cubic grid ΓL\Gamma_L with its vertices, edges, tails and heads, the box constant cc and the giant size bound (7), and over the edge relation (3), connectivity, connected components and giant components of a finite directed multigraph with a set of edges deleted.