The Setting
The structures behind the lower bound for choiceless polynomial time with counting (CPT) are built over the cubic grid of side . The question is isoperimetric. When a set of vertices holds at most half of the grid, how few edges can join to its complement? The bound is the grid analogue of the isoperimetric inequality in space, with an explicit constant.
The library states this bound and, beside it, two counting facts about the projections of a finite set of triples onto pairs of coordinates.
The Grid and Its Edge Boundary
A vertex of the cubic grid of side is a triple of integers in , and the vertex set (1)✦ has elements.
An edge along of the grid is the unit segment joining a vertex with to .✦ Edges along and along are defined likewise, joining to with , or to with . Write , and for the three families. The edge set of the grid is their disjoint union, (2)✦
The tail of a grid edge is the vertex at its lower end✦, and its head is the vertex at its upper end: the tail with the coordinate in the direction of raised by one.✦
The edge boundary of a set of vertices is the set of grid edges with exactly one endpoint in , (3)✦
The box isoperimetric constant is the real number (4)✦
Projections of a Set of Triples
Let , , be sets. For a subset of , the projection of onto the first two coordinates is the subset of (5) and the projections onto the first and third coordinates and onto the last two are defined likewise.
The Claim
Theorem 1. Let , and let be a nonempty set of vertices of the cubic grid of side with . Then (6)✦
Theorem 2 (Loomis-Whitney inequality). Let , , be sets and a finite subset of . Then (7)✦
Theorem 3. Let , and let be a set of vertices of the cubic grid of side . Then each of the three projections of satisfies (8)✦
What Is Checked
The inequalities (6) and (8) are stated over the cubic grid of side : its vertex set , its edges along the three axes with their tails and heads, and the edge boundary defined from them, with (6) also over the constant of (4). The inequality (7) is stated over an arbitrary finite set of triples and its three projections.