OctoInformBeta

OpenAI preprint, September 2026 · §2. The finite complex · §2

Proposition 2.1 [Properties of the complex]: 33 pairs in two faces each, six orderings of eleven faces, and color refinement of HH ending injective on each side

Incidences, orderings and color refinement of the finite complex.

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

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 0,…,120,\dots,12, and 22 faces F0,…,F21F_0,\dots,F_{21}, each a set of three points, in this 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{aligned} &\{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{aligned}(1)✦ A pair of the complex is a two-element set of points contained in some face, and ℰ\mathcal{E} is the set of all pairs: ℰ=⋃j=021(Fj2).\mathcal{E}=\bigcup_{j=0}^{21}\binom{F_j}{2}.(2)✦

The graph HH 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 (j,s)(j,s) consists of a face j∈{0,…,21}j\in\{0,\dots,21\} and a slot s∈{0,1,2}s\in\{0,1,2\}✦; its point v(j,s)v(j,s) is the point in slot ss of FjF_j, 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 HH.

Pairs, Labels and Rows

The pairs carry indices: to each e∈{0,…,32}e\in\{0,\dots,32\} a table assigns a set π(e)\pi(e) of two points, the pair with index ee. Further tables give each pair ee the two faces ϕ0(e)\phi_0(e) and ϕ1(e)\phi_1(e) containing it, a parent ρ(e)\rho(e), which is again a pair (the pair 00 is its own parent and every other pair has a parent of smaller index), and a bridge face β(e)\beta(e), a face containing both the pair ee and its parent ρ(e)\rho(e); and they give each face jj its three pairs ψ0(j)\psi_0(j), ψ1(j)\psi_1(j), ψ2(j)\psi_2(j).

Each face jj carries a bit label ℓ(j)=(ℓ0(j),ℓ1(j),ℓ2(j))∈{0,1}3\ell(j)=(\ell_0(j),\ell_1(j),\ell_2(j))\in\{0,1\}^3, fixed by an explicit list; for each bit position bb, the faces with ℓb(j)=0\ell_b(j)=0 form one class and those with ℓb(j)=1\ell_b(j)=1 the other. The separation count s(e)s(e) of a pair ee is the number of bit positions at which the labels of its two faces differ: s(e)=|{b∈{0,1,2}:ℓb(ϕ0(e))≠ℓb(ϕ1(e))}|.s(e)=\bigl|\{\,b\in\{0,1,2\} : \ell_b(\phi_0(e))\neq\ell_b(\phi_1(e))\,\}\bigr|.(3)✦

Six rows c∈{0,…,5}c\in\{0,\dots,5\} each order eleven faces: at step n∈{0,…,10}n\in\{0,\dots,10\} row cc holds the face Fγc(n)F_{\gamma_c(n)}, where γc(n)\gamma_c(n) is the entry in row cc and column nn, both counted from 00, of (012451614182019133981011171512217602891241156181413721201913101517160139765161415192810114171312212018).\begin{pmatrix} 0&1&2&4&5&16&14&18&20&19&13\\ 3&9&8&10&11&17&15&12&21&7&6\\ 0&2&8&9&12&4&11&5&6&18&14\\ 1&3&7&21&20&19&13&10&15&17&16\\ 0&1&3&9&7&6&5&16&14&15&19\\ 2&8&10&11&4&17&13&12&21&20&18 \end{pmatrix}.(4)✦ A face jj occurs in row cc when j=γc(n)j=\gamma_c(n) for some step nn, and RcR_c is the set of faces occurring in row cc.✦ A pair ee is internal to row cc when both of its faces ϕ0(e)\phi_0(e) and ϕ1(e)\phi_1(e) lie in RcR_c.✦ With each row cc come a map σc\sigma_c from the labels 0,…,120,\dots,12 to the points and, for each step n∈{0,…,9}n\in\{0,\dots,9\}, two labels uc,nu_{c,n} and wc,nw_{c,n} in {0,…,12}\{0,\dots,12\}, a pair gc,ng_{c,n} and a parent step pc,n∈{0,…,10}p_{c,n}\in\{0,\dots,10\} of the step n+1n+1.

Colorings of HH

A coloring of the points is a map κ\kappa from the points to the colors {0,…,34}\{0,\dots,34\}, and a coloring of the faces is a map λ\lambda from the faces to the same colors. The neighbor histogram νλ(x)\nu_\lambda(x) of a point xx under λ\lambda is the function on colors whose value at dd is the number of corners at xx whose face has color dd, and the neighbor histogram μκ(j)\mu_\kappa(j) of a face jj under κ\kappa counts in the same way the corners of jj whose point has color dd: νλ(x)(d)=|{(j,s):v(j,s)=x,λ(j)=d}|,μκ(j)(d)=|{s∈{0,1,2}:κ(v(j,s))=d}|.\nu_\lambda(x)(d)=\bigl|\{(j,s) : v(j,s)=x,\ \lambda(j)=d\}\bigr|,\qquad \mu_\kappa(j)(d)=\bigl|\{s\in\{0,1,2\} : \kappa(v(j,s))=d\}\bigr|.(5)✦

The claim concerns explicit colorings κ0,…,κ4\kappa_0,\dots,\kappa_4 of the points and λ0,…,λ4\lambda_0,\dots,\lambda_4 of the faces. The colorings κ0\kappa_0 and λ0\lambda_0 are constant, with values 00 and 11, one color on each side. Round tt passes from κt\kappa_t and λt\lambda_t to κt+1\kappa_{t+1} and λt+1\lambda_{t+1}, and for the rounds t=0t=0 and t=3t=3 explicit histogram tables give a function ht(x)h_t(x) from colors to nonnegative integers for each point xx, and a function ht′(j)h'_t(j) of the same kind for each face jj.

The Claim

Theorem 1 (Properties of the complex). Let the faces, pairs, rows, colorings and histogram tables be those defined above. For all pairs e≠e′e\neq e', π(e)≠π(e′).\pi(e)\neq\pi(e').(6)✦ For every pair ee and every face jj, π(e)⊆Fj⇔j∈{ϕ0(e),ϕ1(e)},\pi(e)\subseteq F_j\iff j\in\{\phi_0(e),\phi_1(e)\},(7)✦ ϕ0(e)≠ϕ1(e),\phi_0(e)\neq\phi_1(e),(8)✦ π(e)⊆Fj⇔e∈{ψ0(j),ψ1(j),ψ2(j)},\pi(e)\subseteq F_j\iff e\in\{\psi_0(j),\psi_1(j),\psi_2(j)\},(9)✦ and ℰ⊆{π(0),π(1),…,π(32)}.\mathcal{E}\subseteq\{\pi(0),\pi(1),\dots,\pi(32)\}.(10)✦ Every pair e≠0e\neq0 satisfies ρ(e)<e,\rho(e)<e,(11)✦ and every pair ee satisfies π(e)⊆Fβ(e),\pi(e)\subseteq F_{\beta(e)},(12)✦ π(ρ(e))⊆Fβ(e).\pi(\rho(e))\subseteq F_{\beta(e)}.(13)✦ For every row cc, σc is a bijection of {0,…,12},\sigma_c \text{ is a bijection of } \{0,\dots,12\},(14)✦ γc(n)≠γc(n′)(0≤n<n′≤10),\gamma_c(n)\neq\gamma_c(n')\qquad(0\le n<n'\le 10),(15)✦ Fγc(0)={σc(0),σc(1),σc(2)},F_{\gamma_c(0)}=\{\sigma_c(0),\sigma_c(1),\sigma_c(2)\},(16)✦ and at every step n∈{0,…,9}n\in\{0,\dots,9\} Fγc(n+1)={σc(uc,n),σc(wc,n),σc(n+3)},F_{\gamma_c(n+1)}=\{\sigma_c(u_{c,n}),\sigma_c(w_{c,n}),\sigma_c(n+3)\},(17)✦ π(gc,n)⊆Fγc(pc,n),\pi(g_{c,n})\subseteq F_{\gamma_c(p_{c,n})},(18)✦ pc,n≤n.p_{c,n}\le n.(19)✦ For every face jj and every pair ee, |{(c,n)∈{0,…,5}×{0,…,10}:γc(n)=j}|=3,\bigl|\{(c,n)\in\{0,\dots,5\}\times\{0,\dots,10\} : \gamma_c(n)=j\}\bigr|=3,(20)✦ |{c∈{0,…,5}:ϕ0(e)∈Rc and ϕ1(e)∈Rc}|=3−s(e),\bigl|\{c\in\{0,\dots,5\} : \phi_0(e)\in R_c \text{ and } \phi_1(e)\in R_c\}\bigr|=3-s(e),(21)✦ s(e)≥1,s(e)\ge 1,(22)✦ while the pair with index 00 has s(0)=3,s(0)=3,(23)✦ π(0)={0,2}.\pi(0)=\{0,2\}.(24)✦ For all points x,yx,y and faces i,ji,j, κ1(x)=κ1(y)⇔κ0(x)=κ0(y) and h0(x)=h0(y),\kappa_1(x)=\kappa_1(y)\iff \kappa_0(x)=\kappa_0(y)\text{ and }h_0(x)=h_0(y),(25)✦ λ1(i)=λ1(j)⇔λ0(i)=λ0(j) and h0′(i)=h0′(j),\lambda_1(i)=\lambda_1(j)\iff \lambda_0(i)=\lambda_0(j)\text{ and }h'_0(i)=h'_0(j),(26)✦ h0(x)=νλ0(x),h_0(x)=\nu_{\lambda_0}(x),(27)✦ h0′(j)=μκ0(j),h'_0(j)=\mu_{\kappa_0}(j),(28)✦ κ4(x)=κ4(y)⇔κ3(x)=κ3(y) and h3(x)=h3(y),\kappa_4(x)=\kappa_4(y)\iff \kappa_3(x)=\kappa_3(y)\text{ and }h_3(x)=h_3(y),(29)✦ λ4(i)=λ4(j)⇔λ3(i)=λ3(j) and h3′(i)=h3′(j),\lambda_4(i)=\lambda_4(j)\iff \lambda_3(i)=\lambda_3(j)\text{ and }h'_3(i)=h'_3(j),(30)✦ and, when x≠yx\neq y and i≠ji\neq j, κ4(x)≠κ4(y),\kappa_4(x)\neq\kappa_4(y),(31)✦ λ4(i)≠λ4(j).\lambda_4(i)\neq\lambda_4(j).(32)✦

In the paper, the result reads: every pair in ℰ\mathcal{E} lies in exactly two faces, |ℰ|=33|\mathcal{E}|=33, 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 ae=s(e)/3a_e=s(e)/3, every ae≥1/3a_e\ge 1/3, and some ae>1/3a_e>1/3; and color refinement of HH, 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 σc\sigma_c, labels, pairs and parent steps, and the colorings of HH with their histogram tables and the neighbor histograms (5).