The Setting
For a natural number , the cubic grid of side has as vertices the integer triples (1) and the structures of the separation of choiceless polynomial time with counting from polynomial time, one for each charge (a function from to ), are built on .
The edges of are the unit segments parallel to the coordinate axes, each given by its lower endpoint: (2)✦ with and the same products with the short range in the second and in the third place. The edge given by runs from its tail to its head ; the edges of and given by run from to and to .
Delete a set of edges from . The question is whether, for small against , the remaining graph 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 be a finite directed multigraph: a finite set of vertices, a finite set of edges, and for each edge a tail and a head in . The grid is one, with the tails and heads above.
For a set , the edge relation of is the binary relation on given by (3)✦ Connectivity in is the smallest equivalence relation on containing .✦ A connected component of is an equivalence class of ✦, and the component of a vertex is the class containing it: (4)✦ A vertex of lies in a giant component of when its component holds more than half of the vertices: (5)✦
The Size Condition
The box isoperimetric constant is the real number (6)✦ A pair of natural numbers satisfies the giant size bound when, with , (7)
The Claim
Theorem 1. Let and let be a set of edges of the cubic grid .
If is a set of connected components of , each with at most vertices, then (8)✦
If , then has a connected component with (9)✦
If and satisfy the giant size bound (7) and , then there is a vertex of with (10)✦
In any finite directed multigraph with vertex set , if are sets of edges and is a vertex with , then (11)✦
In the paper, the result reads: for large and a set of at most deleted edges, a unique component of has more than vertices, and it shrinks monotonically as more edges are deleted.
The giant size bound (7) takes the place of the paper’s choice with large.
What Is Checked
The claim is stated over the cubic grid with its vertices, edges, tails and heads, the box constant 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.