OctoInformBeta

OpenAI preprint, September 2026 · §2. A finite colored-graph characterization · §2

Definition 2.1 (setting): admissible placements, Γ_S and a_S: Self-maps of a vertex set that never raise an edge’s color carry the seed edges SS to the marked edges of ΓS\Gamma_S

Admissible self-maps and the marked graph of a coloring.

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

Take a finite algebra AA and give the edge (p,q)(p,q) between two of its elements the color Cg(p,q)\mathrm{Cg}(p,q), the principal congruence of the pair, an element of Con(A)\mathrm{Con}(A). A one-variable translation ff of an operation of AA never raises a color, Cg(f(p),f(q))≤Cg(p,q)\mathrm{Cg}(f(p),f(q)) \le \mathrm{Cg}(p,q), and it may collapse an edge to a loop. Which edges can such maps reach from a few given ones, and which elements do the reached edges link? The same questions make sense for an arbitrary coloring, with every self-map that never raises a color in place of the translations.

Colorings

For a set LL with a relation ≤\le, a lattice with its order for instance, an LL-coloring of a set AA of vertices is any map d:A×A→Ld \colon A \times A \to L; the value d(p,q)d(p,q) is the color of the edge (p,q)(p,q), and loops (p,p)(p,p) count as edges.

The Definition

Definition 1. Let dd be an LL-coloring of a set AA. A self-map f:A→Af \colon A \to A, not necessarily injective, is admissible when d(f(p),f(q))≤d(p,q)for all p,q∈A.d(f(p),f(q)) \le d(p,q) \qquad \text{for all } p, q \in A.(1)✦ For a finite set S⊆A×AS \subseteq A \times A of seed edges, the marked edges of the graph ΓS\Gamma_S on AA are the images of seeds under admissible self-maps: MS={(f(p),f(q)):f:A→A admissible,(p,q)∈S}.M_S = \{(f(p),f(q)) : f \colon A \to A \text{ admissible},\ (p,q) \in S\}.(2)✦ Two vertices pp and qq are connected in ΓS\Gamma_S, written p∼Sqp \sim_S q, when they lie in one class of the equivalence relation on AA generated by MSM_S: for some k≥0k \ge 0 there are vertices x0,…,xkx_0, \dots, x_k with x0=p,xk=q,(xi−1,xi)∈MS or (xi,xi−1)∈MS for 1≤i≤k.x_0 = p, \quad x_k = q, \quad (x_{i-1},x_i) \in M_S \text{ or } (x_i,x_{i-1}) \in M_S \ \text{ for } 1 \le i \le k.(3)✦

In the paper, the definition reads: an LL-colored complete graph is a finite nonempty vertex set AA with a symmetric d:A×A→Ld \colon A \times A \to L and d(p,p)=0d(p,p) = 0, the least element of LL, loops being edges; a placement f:A→A′f \colon A \to A' into another such graph (A′,d′)(A',d') is admissible when d′(f(p),f(q))≤d(p,q)d'(f(p),f(q)) \le d(p,q) for all p,q∈Ap, q \in A; for a nonempty set SS of edges, ΓS\Gamma_S is the undirected graph on AA whose marked adjacencies are the pairs {f(p),f(q)}\{f(p),f(q)\} with {p,q}∈S\{p,q\} \in S and f:A→Af \colon A \to A admissible, collapsed pairs allowed; and aS=⋁{p,q}∈Sd(p,q)a_S = \bigvee_{\{p,q\} \in S} d(p,q).

What Is Checked

Admissibility (1), the marked edges (2) and connectedness in ΓS\Gamma_S (3) are defined over any set AA of vertices, any set LL with a relation ≤\le, any LL-coloring dd of AA and, for the last two, any finite set SS of ordered pairs of vertices as seeds.