OctoInformBeta

OpenAI preprint, September 2026 · Section 3. Colored graphs and the bounded block

Section 3 (setting): quantitative scales, capped labels and anchors: Capped color distances and integer edge lengths specify the block metric and its shortest source paths

Scales and anchors for a metric block.

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

The bounded metric block is geometric data for the Lipschitz-free construction. Its original points come from a colored graph with reversible ports.

A graph GG with reversible ports on a vertex set XX has a port set PP, a reversal r:P→Pr:P\to P, and moves me:X→Xm_e:X\to X satisfying (1). r(r(e))=e,mr(e)(me(x))=x(x∈X,e∈P).r(r(e))=e,\qquad m_{r(e)}(m_e(x))=x \quad (x\in X,\ e\in P).(1)✦ A port walk w=(e1,…,en)w=(e_1,\ldots,e_n) in GG is a finite sequence of ports, whose moves are followed in order; write G(x,w)G(x,w) for its endpoint when it starts at x∈Xx\in X, with G(x,⌀)=xG(x,\varnothing)=x. Vertices x,y∈Xx,y\in X are adjacent, written x∼yx\sim y, when me(x)=ym_e(x)=y for some e∈Pe\in P.✦

Let CC be a finite color set and c:X→Cc:X\to C a coloring. For a finite color set CC and a nonnegative integer cap DD, the box ℬD(C)\mathcal B_D(C) of bounded color coordinates is the set of functions in (2). ℬD(C)={a:C→{0,1,…,D}}.\mathcal B_D(C)=\{a:C\to\{0,1,\ldots,D\}\}.(2) The distance between box labels is their supremum distance (3). ∥a−b∥∞=maxi∈C|a(i)−b(i)|,max⁡⌀=0.\|a-b\|_\infty=\max_{i\in C}|a(i)-b(i)|, \qquad \max\varnothing=0.(3)✦

For a nonnegative integer parameter pp, the block diameter bound BpB_p is the polynomial in (4). Bp=300p2+150p+5.B_p=300p^2+150p+5.(4)✦

Let YY be a set, let u,v∈Yu,v\in Y, and let w:Y×Y→ℕw:Y\times Y\to\mathbb N be a nonnegative integer weight. The weighted length 𝖼w(u,v;z1,…,zm)\mathsf c_w(u,v;z_1,\ldots,z_m) of a list z1,…,zm∈Yz_1,\ldots,z_m\in Y of intermediate points is the sum in (5), where z0=uz_0=u and zm+1=vz_{m+1}=v. 𝖼w(u,v;z1,…,zm)=∑j=0mw(zj,zj+1).\mathsf c_w(u,v;z_1,\ldots,z_m) =\sum_{j=0}^{m}w(z_j,z_{j+1}).(5) The minimum path length dw:Y×Y→ℕd_w:Y\times Y\to\mathbb N is the function given by (6). dw(u,v)=min⁡{𝖼w(u,v;z1,…,zm):m≥0,(z1,…,zm)∈Ym}.d_w(u,v)=\min\bigl\{\mathsf c_w(u,v;z_1,\ldots,z_m): m\ge0,\ (z_1,\ldots,z_m)\in Y^m\bigr\}.(6) For a symmetric weight vanishing exactly on the diagonal, this minimum path length is the induced path metric.✦

The Claim

Theorem 1. Fix an integer p≥1p\ge1. The local radius LL and attachment scale RR are given by (7) and (8). L=10p.L=10p.(7)✦ R=3L.R=3L.(8)✦ Define the scale KK and label cap DD by (9) and (10). K=10p(R+1).K=10p(R+1).(9)✦ D=K+2L+5.D=K+2L+5.(10)✦ The identity (12) between the block scale in (11) and the block diameter bound holds for every nonnegative integer pp. B=4R+D.B=4R+D.(11)✦ B=Bp.B=B_p.(12)✦ The auxiliary bound VV, number of generators gg, and graph degree bound Δ\Delta are given by (13), (14), and (15), respectively. V=1+4pB.V=1+4pB.(13)✦ g=20V+2.g=20V+2.(14)✦ Δ=2g.\Delta=2g.(15)✦ Take the local ball bound QQ and ball bound HH as in (16) and (17). Q=Δ2L+1.Q=\Delta^{2L+1}.(16)✦ H=ΔD+1.H=\Delta^{D+1}.(17)✦ The number of colors kk is specified in (18). k=2ΔQH+1.k=2\Delta QH+1.(18)✦

For the metric construction, let GG be any graph with reversible ports on XX, let CC be any finite color set, and let c:X→Cc:X\to C be a coloring. Allow any integer cap D≥0D\ge0 and any integer attachment length R>0R>0. For a vertex x∈Xx\in X and a color i∈Ci\in C, the capped distance λi(x)\lambda_i(x) from xx to color ii is the least integer in (19). λi(x)=min⁡({D}∪{n∈ℕ:∃w∈Pn,c(G(x,w))=i}).\lambda_i(x)=\min\Bigl(\{D\}\cup \{n\in\mathbb N:\exists w\in P^n,\ c(G(x,w))=i\}\Bigr).(19)✦ The vertex distance profile ℓ(x)∈ℬD(C)\ell(x)\in\mathcal B_D(C) of x∈Xx\in X is the function on CC given by (20). ℓ(x)(i)=λi(x)(i∈C).\ell(x)(i)=\lambda_i(x)\qquad(i\in C).(20) The set AA of realized label anchors is the subset of ℬD(C)\mathcal B_D(C) given by (21). A={a∈ℬD(C):∃x∈X,ℓ(x)=a}.A=\{a\in\mathcal B_D(C):\exists x\in X,\ \ell(x)=a\}.(21)✦ The anchor α(x)∈A\alpha(x)\in A of a vertex x∈Xx\in X is the label ℓ(x)\ell(x). The set MM of metric points is the disjoint union of XX and AA in (22). M=X⊔A.M=X\sqcup A.(22) The vertex inclusion ιX:X→M\iota_X:X\to M and anchor inclusion ιA:A→M\iota_A:A\to M send each element to its copy in the corresponding part of MM; use xx and aa also for these images. The block edge weight w:M×M→ℕw:M\times M\to\mathbb N is the function in (23). w(u,v)={0,u=v,1,u=x,v=y,x,y∈X,x≠y,x∼y,R,{u,v}={x,α(x)} for some x∈X,2R+∥a−b∥∞,u=a,v=b,a,b∈A,a≠b,4R+D,otherwise.w(u,v)= \begin{cases} 0,&u=v,\\ 1,&u=x,\ v=y,\ x,y\in X,\ x\ne y,\ x\sim y,\\ R,&\{u,v\}=\{x,\alpha(x)\}\text{ for some }x\in X,\\ 2R+\|a-b\|_\infty,&u=a,\ v=b,\ a,b\in A,\ a\ne b,\\ 4R+D,&\text{otherwise}. \end{cases}(23) The block metric dd on MM is the minimum path metric in (24). d(u,v)=dw(u,v).d(u,v)=d_w(u,v).(24)✦ A source path γ\gamma in MM is a finite concatenation of original adjacent vertex edges of length 11, attachments xx to α(x)\alpha(x) in either direction of length RR, and edges between distinct anchors a,ba,b of length 2R+∥a−b∥∞2R+\|a-b\|_\infty; its length is the sum of its edge lengths, and the constant path has length zero. Write 𝒮(u,v)\mathcal S(u,v) for the source paths from uu to vv. Given u,v∈Mu,v\in M, there is a source path γ∈𝒮(u,v)\gamma\in\mathcal S(u,v) whose length satisfies (25). length⁡(γ)=d(u,v).\operatorname{length}(\gamma)=d(u,v).(25)✦

In the paper, the result reads: fix an integer p≥1p\ge1, put L=10pL=10p, R=3LR=3L, K=10p(R+1)K=10p(R+1), D=K+2L+5D=K+2L+5, B=4R+DB=4R+D and V=1+4pBV=1+4pB; choose an even Δ≥4\Delta\ge4 with V/Δ<1/20V/\Delta<1/20, put Q=Δ2L+1Q=\Delta^{2L+1} and H=ΔD+1H=\Delta^{D+1}, and choose k>2ΔQHk>2\Delta QH; label each source vertex by its distances to the color classes capped at DD, add one anchor for each realized label, attach each source vertex to its anchor by an edge of length RR, join distinct anchors with labels v,wv,w by an edge of length 2R+∥v−w∥∞2R+\|v-w\|_\infty, and take only vertices as metric points.

What Is Checked

The scale definitions concern integers p≥1p\ge1; the metric and shortest path assertions are stated over any reversible port graph, any finite color set and coloring, any nonnegative integer cap DD, and any positive integer attachment length RR. The block weight is symmetric✦, vanishes on the diagonal✦, and vanishes only when its endpoints agree.✦