The Setting
Proposition 2.1 is a list of finite facts about a small two-dimensional complex and the graph of incidences between its points and its faces. The complex has 13 points, labelled , and 22 faces , each a set of three points, in this order: (1)✦ A pair of the complex is a two-element set of points contained in some face, and is the set of all pairs: (2)✦
The graph is the bipartite graph whose two sides are the 13 points and the 22 faces, a point being joined to each face that contains it. A corner consists of a face and a slot ✦; its point is the point in slot of , the face vertex table listing the three points of each face in increasing order. The 66 corners are the incidences between points and faces, one for each edge of .
Pairs, Labels and Rows
The pairs carry indices: to each a table assigns a set of two points, the pair with index . Further tables give each pair the two faces and containing it, a parent , which is again a pair (the pair is its own parent and every other pair has a parent of smaller index), and a bridge face , a face containing both the pair and its parent ; and they give each face its three pairs , , .
Each face carries a bit label , fixed by an explicit list; for each bit position , the faces with form one class and those with the other. The separation count of a pair is the number of bit positions at which the labels of its two faces differ: (3)✦
Six rows each order eleven faces: at step row holds the face , where is the entry in row and column , both counted from , of (4)✦ A face occurs in row when for some step , and is the set of faces occurring in row .✦ A pair is internal to row when both of its faces and lie in .✦ With each row come a map from the labels to the points and, for each step , two labels and in , a pair and a parent step of the step .
Colorings of
A coloring of the points is a map from the points to the colors , and a coloring of the faces is a map from the faces to the same colors. The neighbor histogram of a point under is the function on colors whose value at is the number of corners at whose face has color , and the neighbor histogram of a face under counts in the same way the corners of whose point has color : (5)✦
The claim concerns explicit colorings of the points and of the faces. The colorings and are constant, with values and , one color on each side. Round passes from and to and , and for the rounds and explicit histogram tables give a function from colors to nonnegative integers for each point , and a function of the same kind for each face .
The Claim
Theorem 1 (Properties of the complex). Let the faces, pairs, rows, colorings and histogram tables be those defined above. For all pairs , (6)✦ For every pair and every face , (7)✦ (8)✦ (9)✦ and (10)✦ Every pair satisfies (11)✦ and every pair satisfies (12)✦ (13)✦ For every row , (14)✦ (15)✦ (16)✦ and at every step (17)✦ (18)✦ (19)✦ For every face and every pair , (20)✦ (21)✦ (22)✦ while the pair with index has (23)✦ (24)✦ For all points and faces , (25)✦ (26)✦ (27)✦ (28)✦ (29)✦ (30)✦ and, when and , (31)✦ (32)✦
In the paper, the result reads: every pair in lies in exactly two faces, , and the face-neighbor graph, in which two faces are adjacent when they share a pair, is connected; for each bit position, each of its two classes consists of 11 faces covering all 13 points and has an ordering in which every face after the first shares a pair with an earlier face and introduces exactly one new point; with , every , and some ; and color refinement of , starting with one color per part, eventually gives distinct colors to all vertices within either part; here the orderings of the six classes are the rows of (4).
What Is Checked
The claim is stated over the faces (1) and the pairs (2) of the complex, the indexed pairs with their two faces, parents and bridge faces, the three pairs listed for each face, the bit labels with the separation count (3), the six rows (4) with their maps , labels, pairs and parent steps, and the colorings of with their histogram tables and the neighbor histograms (5).