OctoInformBeta

OpenAI preprint, September 2026 · §3. Constructing a negative kernel correlation · §3

Lemma 3.4 [Pinning by vertex and pair scores]: Scores maximized exactly at map pairs preserving a colouring give scores maximized exactly at those preserving its refinement; on the 13-point graph, at the identity alone

Scores that pin the identity on 13 points and 22 faces.

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

Let FF be a finite bipartite graph with parts II and JJ and edge set EE, the edge ee joining the vertex t(e)t(e) of II to the vertex h(e)h(e) of JJ. Real scores on the vertices of FF and on the pairs in I×JI\times J give every pair of maps a:I→Ia\colon I\to I, b:J→Jb\colon J\to J a total score. A system ss of vertex and pair scores on FF pins the identity if the identity pair (id,id)(\mathrm{id},\mathrm{id}) is the only pair of maps a:I→Ia\colon I\to I, b:J→Jb\colon J\to J of largest score under ss. Lemma 3.4 is about the pairs of largest score: how they follow colour refinement on FF, and, for one bipartite graph HH on 13 points and 22 faces, whether some scores pin the identity.

The graph HH is the bipartite graph on the 13 points 0,…,120,\dots,12 and the 22 faces 0,…,210,\dots,21 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: (0,1,3),(0,1,9),(0,2,3),(0,2,9),(1,3,10),(1,7,10),(1,7,12),(1,9,12),(2,3,4),(2,4,9),(3,4,11),(3,10,11),(4,8,9),(4,8,11),(5,6,7),(5,6,11),(5,7,10),(5,10,11),(6,7,12),(6,8,11),(6,8,12),(8,9,12).\begin{gathered} (0,1,3),\ (0,1,9),\ (0,2,3),\ (0,2,9),\ (1,3,10),\ (1,7,10),\ (1,7,12),\ (1,9,12),\\ (2,3,4),\ (2,4,9),\ (3,4,11),\ (3,10,11),\ (4,8,9),\ (4,8,11),\ (5,6,7),\\ (5,6,11),\ (5,7,10),\ (5,10,11),\ (6,7,12),\ (6,8,11),\ (6,8,12),\ (8,9,12). \end{gathered}(1) A corner of HH is a pair (j,ℓ)(j,\ell) of a face jj and a slot ℓ∈{0,1,2}\ell\in\{0,1,2\}✦, and its point v(j,ℓ)v(j,\ell) is the point in slot ℓ\ell of the face jj in (1).✦ In the notation above, HH has the points as II, the faces as JJ and the 66 corners as EE, the corner (j,ℓ)(j,\ell) joining its point v(j,ℓ)v(j,\ell) to the face jj.

Scores and Colour Refinement

A system ss of vertex and pair scores on finite sets II and JJ is a triple of real functions: i↦s(i)i\mapsto s(i) on II, j↦s(j)j\mapsto s(j) on JJ and (i,j)↦s(i,j)(i,j)\mapsto s(i,j) on I×JI\times J.✦ For the graph FF, the score of a pair (a,b)(a,b) of maps a:I→Ia\colon I\to I and b:J→Jb\colon J\to J under ss adds the vertex scores of the images of the vertices and the pair scores of the images of the edges: 𝒬s(a,b)=∑i∈Is(a(i))+∑j∈Js(b(j))+∑e∈Es(a(t(e)),b(h(e))).\mathcal{Q}_s(a,b)=\sum_{i\in I}s\bigl(a(i)\bigr)+\sum_{j\in J}s\bigl(b(j)\bigr) +\sum_{e\in E}s\bigl(a(t(e)),\,b(h(e))\bigr).(2)✦

Let cIc_I be a colouring of II and cJc_J a colouring of JJ, both by a set CC of colours. A pair (a,b)(a,b) of maps a:I→Ia\colon I\to I and b:J→Jb\colon J\to J preserves (cI,cJ)(c_I,c_J) if cI(a(i))=cI(i)c_I(a(i))=c_I(i) for every i∈Ii\in I and cJ(b(j))=cJ(j)c_J(b(j))=c_J(j) for every j∈Jj\in J.✦

The neighbour histogram of a vertex i∈Ii\in I for cJc_J is the function NcJ(i)N_{c_J}(i) on CC that counts, for each colour xx, the edges at ii whose end in JJ has colour xx: NcJ(i)(x)=|{e∈E:t(e)=i,cJ(h(e))=x}|.N_{c_J}(i)(x)=\bigl|\{e\in E: t(e)=i,\ c_J(h(e))=x\}\bigr|.(3)✦ The neighbour histogram of a vertex j∈Jj\in J for cIc_I is the function NcI(j)N_{c_I}(j) on CC that counts, for each colour xx, the edges at jj whose end in II has colour xx.

A pair of colourings dId_I of II and dJd_J of JJ by CC arises from (cI,cJ)(c_I,c_J) by one round of colour refinement if, for all vertices v,w∈Iv,w\in I, dI(v)=dI(w)⇔cI(v)=cI(w)andNcJ(v)=NcJ(w),d_I(v)=d_I(w)\iff c_I(v)=c_I(w)\ \text{and}\ N_{c_J}(v)=N_{c_J}(w),(4) and, for all vertices v,w∈Jv,w\in J, dJ(v)=dJ(w)d_J(v)=d_J(w) exactly when cJ(v)=cJ(w)c_J(v)=c_J(w) and NcI(v)=NcI(w)N_{c_I}(v)=N_{c_I}(w).

The Claim

Theorem 1. (a) Let FF be a finite bipartite graph with parts II and JJ, let cI,dIc_I,d_I be colourings of II and cJ,dJc_J,d_J colourings of JJ by a set CC, and suppose that (dI,dJ)(d_I,d_J) arises from (cI,cJ)(c_I,c_J) by one round of colour refinement (4). If a system ss of vertex and pair scores on II and JJ satisfies 𝒬s(a,b)≤𝒬s(id,id)\mathcal{Q}_s(a,b)\le\mathcal{Q}_s(\mathrm{id},\mathrm{id}) for every pair (a,b)(a,b) of maps a:I→Ia\colon I\to I and b:J→Jb\colon J\to J, with equality exactly when (a,b)(a,b) preserves (cI,cJ)(c_I,c_J), then there is a system s′s' of vertex and pair scores on II and JJ such that, for every such pair (a,b)(a,b), 𝒬s′(a,b)≤𝒬s′(id,id),with equality exactly when (a,b) preserves (dI,dJ).\mathcal{Q}_{s'}(a,b)\le\mathcal{Q}_{s'}(\mathrm{id},\mathrm{id}),\quad \text{with equality exactly when $(a,b)$ preserves $(d_I,d_J)$.}(5)✦

(b) There is a system ss of vertex and pair scores on the points and the faces of HH such that every pair (a,b)(a,b) other than (id,id)(\mathrm{id},\mathrm{id}), of a map aa from the points to themselves and a map bb from the faces to themselves, has 𝒬s(a,b)<𝒬s(id,id).\mathcal{Q}_s(a,b)<\mathcal{Q}_s(\mathrm{id},\mathrm{id}).(6)✦

In the paper, the result reads: if FF is a finite bipartite graph with parts PP and QQ and edge set LL for which colour refinement from the two part colours becomes discrete within each part, then there are vertex scores sts_t and pair scores sabs_{ab} such that the identity is the unique maximizer, with a positive gap, of 𝒬(f)=∑usf(u)+∑uv∈Lsf(u)f(v)\mathcal{Q}(f)=\sum_u s_{f(u)}+\sum_{uv\in L}s_{f(u)f(v)} over all part-preserving maps ff, with PP, QQ and LL in the roles of II, JJ and EE.

The statement (6) is that conclusion for F=HF=H, with the points as PP and the faces as QQ.

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 HH, whose edges are the corners of the faces in (1) and their points.