The Setting
Let be a finite bipartite graph with parts and and edge set , the edge joining the vertex of to the vertex of . Real scores on the vertices of and on the pairs in give every pair of maps , a total score. A system of vertex and pair scores on pins the identity if the identity pair is the only pair of maps , of largest score under . Lemma 3.4 is about the pairs of largest score: how they follow colour refinement on , and, for one bipartite graph on 13 points and 22 faces, whether some scores pin the identity.
The graph is the bipartite graph on the 13 points and the 22 faces that joins each point to the faces containing it. Each face is a triple of points, and the faces are the following triples, each written with its points in increasing order: (1) A corner of is a pair of a face and a slot ✦, and its point is the point in slot of the face in (1).✦ In the notation above, has the points as , the faces as and the 66 corners as , the corner joining its point to the face .
Scores and Colour Refinement
A system of vertex and pair scores on finite sets and is a triple of real functions: on , on and on .✦ For the graph , the score of a pair of maps and under adds the vertex scores of the images of the vertices and the pair scores of the images of the edges: (2)✦
Let be a colouring of and a colouring of , both by a set of colours. A pair of maps and preserves if for every and for every .✦
The neighbour histogram of a vertex for is the function on that counts, for each colour , the edges at whose end in has colour : (3)✦ The neighbour histogram of a vertex for is the function on that counts, for each colour , the edges at whose end in has colour .
A pair of colourings of and of by arises from by one round of colour refinement if, for all vertices , (4) and, for all vertices , exactly when and .
The Claim
Theorem 1. (a) Let be a finite bipartite graph with parts and , let be colourings of and colourings of by a set , and suppose that arises from by one round of colour refinement (4). If a system of vertex and pair scores on and satisfies for every pair of maps and , with equality exactly when preserves , then there is a system of vertex and pair scores on and such that, for every such pair , (5)✦
(b) There is a system of vertex and pair scores on the points and the faces of such that every pair other than , of a map from the points to themselves and a map from the faces to themselves, has (6)✦
In the paper, the result reads: if is a finite bipartite graph with parts and and edge set for which colour refinement from the two part colours becomes discrete within each part, then there are vertex scores and pair scores such that the identity is the unique maximizer, with a positive gap, of over all part-preserving maps , with , and in the roles of , and .
The statement (6) is that conclusion for , with the points as and the faces as .
What Is Checked
The claim (5) is stated over the vertex and pair scores on the two parts of a finite bipartite graph, the score (2), the pairs of maps preserving a pair of colourings and the neighbour histograms (3); the claim (6) is stated over the same scores for , whose edges are the corners of the faces in (1) and their points.