OctoInformBeta

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

Lemma 3.2: A 11-Lipschitz label map and finite color supports accompany separation and diameter bounds

The bounded block has controlled neighborhoods.

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

A metric block for a Lipschitz-free space is built from a colored graph by adjoining points indexed by truncated distances to colors. The geometric quantities at issue are the distances between the two kinds of points and the sizes of short neighborhoods.

A graph GG with reversible ports on a set XX and finite port set PP consists of a move map m:X×P→Xm:X\times P\to X and an involution r:P→Pr:P\to P such that m(m(x,e),r(e))=xm(m(x,e),r(e))=x.✦ A port word ww is a finite list of elements of PP; its endpoint GwxG_wx is obtained by following its ports in order, with the empty word ending at xx.✦ For n∈ℕn\in\mathbb N, the bounded word set 𝒲n(P)\mathcal W_n(P) is the set of port words of length at most nn✦, and the bounded walk relation x∼nyx\sim_n y means reachability along such a word, as in (1).✦ 𝒲n(P)={w:|w|≤n},x∼ny⇔there is w∈𝒲n(P) with Gwx=y.\mathcal W_n(P)=\{w:|w|\le n\}, \qquad x\sim_n y\quad\Longleftrightarrow\quad \text{there is }w\in\mathcal W_n(P)\text{ with }G_wx=y.(1) Vertices x,y∈Xx,y\in X are adjacent in GG if y=m(x,e)y=m(x,e) for some port e∈Pe\in P.

Fix a finite nonempty color set CC, a coloring c:X→Cc:X\to C, an integer cap D≥0D\ge0 and an integer attachment scale R≥1R\ge1. A box label bb on CC with cap DD is a function from CC to {0,…,D}\{0,\ldots,D\}.✦ The supremum distance between box labels a,ba,b is the metric in (2). ∥a−b∥∞=maxi∈C|a(i)−b(i)|.\|a-b\|_\infty=\max_{i\in C}|a(i)-b(i)|.(2)✦ The vertex distance profile ℓX:X→{0,…,D}C\ell_X:X\to\{0,\ldots,D\}^{C} is the map assigning to xx the truncated distances to the colors in (3).✦ ℓX(x)(i)=min⁡({D}∪{|w|:c(Gwx)=i}).\ell_X(x)(i)= \min\bigl(\{D\}\cup\{|w|:c(G_wx)=i\}\bigr).(3)

The realized label anchor set 𝒜\mathcal A is the range ℓX(X)\ell_X(X), and the graph with label anchors MM is the disjoint union X⊔𝒜X\sqcup\mathcal A. Write ι:X→M\iota:X\to M and α:𝒜→M\alpha:\mathcal A\to M for the source vertex and anchor inclusions. The vertex label anchor a(x)∈𝒜a(x)\in\mathcal A is the realized profile of xx✦; the block label ℓ:M→{0,…,D}C\ell:M\to\{0,\ldots,D\}^{C} is the map in (4). a(x)=ℓX(x)∈𝒜,ℓ(ι(x))=ℓX(x),ℓ(α(b))=b(b∈𝒜).a(x)=\ell_X(x)\in\mathcal A, \qquad \ell(\iota(x))=\ell_X(x), \qquad \ell(\alpha(b))=b\quad(b\in\mathcal A).(4)

The block edge weight w:M×M→ℕw:M\times M\to\mathbb N is zero on the diagonal. For distinct endpoints in MM, the block edge weight w:M×M→ℕw:M\times M\to\mathbb N is given by (5), with the same weight in the reverse direction. w(ι(x),ι(y))={1,x,y are adjacent,4R+D,otherwise,w(ι(x),α(b))={R,ℓX(x)=b,4R+D,otherwise,w(α(b),α(b′))=2R+∥b−b′∥∞.\begin{aligned} w(\iota(x),\iota(y))&= \begin{cases}1,&x,y\text{ are adjacent},\\4R+D,&\text{otherwise},\end{cases}\\ w(\iota(x),\alpha(b))&= \begin{cases}R,&\ell_X(x)=b,\\4R+D,&\text{otherwise},\end{cases}\\ w(\alpha(b),\alpha(b'))&=2R+\|b-b'\|_\infty. \end{aligned}(5) The weighted path length cwc_w of a finite path is the sum of successive edge weights.✦ The minimum path distance d(u,v)d(u,v) between u,v∈Mu,v\in M is the least sum of successive edge weights along a finite path from uu to vv, as in (6), where z0=uz_0=u and zq+1=vz_{q+1}=v.✦ cw(u,v;z1,…,zq)=∑t=0qw(zt,zt+1),d(u,v)=minq≥0,z1,…,zq∈Mcw(u,v;z1,…,zq).\begin{aligned} c_w(u,v;z_1,\ldots,z_q)&=\sum_{t=0}^{q}w(z_t,z_{t+1}),\\ d(u,v)&=\min_{q\ge0,\ z_1,\ldots,z_q\in M} c_w(u,v;z_1,\ldots,z_q). \end{aligned}(6)

The short graph relation 𝒮n\mathcal S_n on MM is bounded walk reachability on source vertices and equality on anchors, with no mixed pairs, as in (7).✦ 𝒮n={(ι(x),ι(y)):x∼ny}∪{(α(b),α(b)):b∈𝒜}.\mathcal S_n= \{(\iota(x),\iota(y)):x\sim_n y\} \cup\{(\alpha(b),\alpha(b)):b\in\mathcal A\}.(7) The support colors supp⁡D(u)⊆C\operatorname{supp}_D(u)\subseteq C of a point u∈Mu\in M are the coordinates of its label below the cap, as in (8).✦ For an integer local radius L≥0L\ge0, the transition relation ⤳L\leadsto_L on MM consists of pairs at distance at most 2L2L.✦ supp⁡D(u)={i∈C:ℓ(u)(i)<D},j⤳Lk⇔d(j,k)≤2L.\operatorname{supp}_D(u)=\{i\in C:\ell(u)(i)<D\}, \qquad j\leadsto_L k\quad\Longleftrightarrow\quad d(j,k)\le2L.(8)

The Block Construction

For an integer block parameter p≥1p\ge1, the construction uses local radius LpL_p and attachment scale RpR_p. Its label cap is DpD_p; the auxiliary scales are KpK_p and BpB_p, with auxiliary bound VpV_p. The generator count gpg_p determines the graph degree bound Δp\Delta_p. The local ball and label support bounds are QpQ_p and HpH_p, and kpk_p is the color count. These integers are defined by (9). Lp=10p,Rp=3Lp,Kp=10p(Rp+1),Dp=Kp+2Lp+5,Bp=4Rp+Dp=300p2+150p+5,Vp=1+4pBp,gp=20Vp+2,Δp=2gp,Qp=Δp2Lp+1,Hp=ΔpDp+1,kp=2ΔpQpHp+1.\begin{aligned} L_p&=10p,&R_p&=3L_p,&K_p&=10p(R_p+1),\\ D_p&=K_p+2L_p+5,& B_p&=4R_p+D_p=300p^2+150p+5,\\ V_p&=1+4pB_p,&g_p&=20V_p+2,&\Delta_p&=2g_p,\\ Q_p&=\Delta_p^{\,2L_p+1},&H_p&=\Delta_p^{\,D_p+1},& k_p&=2\Delta_p Q_p H_p+1. \end{aligned}(9) The block generator set is Ap={0,…,gp−1}A_p=\{0,\ldots,g_p-1\}✦ and the block color set is Cp={0,…,kp−1}C_p=\{0,\ldots,k_p-1\}.✦

For a finite generator set AA, let 𝔽(A)\mathbb F(A) be the free group on AA. For an integer N≥0N\ge0, the word ball WN(A)W_N(A) in the free group 𝔽(A)\mathbb F(A) is the set of elements of reduced word length at most NN.✦ The word ball permutation group ΓN(A)\Gamma_N(A) is the group of all permutations of WN(A)W_N(A), as in (10).✦ For a generator a∈Aa\in A, an extended generator translation σN,a∈ΓN(A)\sigma_{N,a}\in\Gamma_N(A) is a permutation agreeing with left multiplication by aa wherever the product stays in WN(A)W_N(A).✦ For a choice of extended generator translations, the word ball permutation representation ρN\rho_N is the homomorphism specified in (10). WN(A)={g∈𝔽(A):|g|≤N},ΓN(A)=Sym⁡(WN(A)),ρN:𝔽(A)→ΓN(A),ρN(a)=σN,a(a∈A).\begin{gathered} W_N(A)=\{g\in\mathbb F(A):|g|\le N\}, \qquad\Gamma_N(A)=\operatorname{Sym}(W_N(A)),\\ \rho_N:\mathbb F(A)\longrightarrow\Gamma_N(A), \qquad\rho_N(a)=\sigma_{N,a}\quad(a\in A). \end{gathered}(10)

A signed port is a pair e=(a,ε)∈A×{−1,1}e=(a,\varepsilon)\in A\times\{-1,1\}, with signed generator aεa^\varepsilon; port reversal changes the sign.✦ The finite Cayley graph on ΓN(A)\Gamma_N(A) has move γ↦γρN(aε)\gamma\mapsto\gamma\rho_N(a^\varepsilon).✦ For a color set CC, the graph of all colorings at radius NN has vertices (χ,γ)(\chi,\gamma) with χ:ΓN(A)→C\chi:\Gamma_N(A)\to C and keeps χ\chi fixed under each move.✦ The union of colored Cayley graphs has vertex set X(A,C)X(A,C) and componentwise coloring cc given by (11); each move keeps the radius NN fixed. X(A,C)=⨆N≥0(CΓN(A)×ΓN(A)),c(N,χ,γ)=χ(γ).X(A,C)=\bigsqcup_{N\ge0}\bigl(C^{\Gamma_N(A)}\times\Gamma_N(A)\bigr), \qquad c(N,\chi,\gamma)=\chi(\gamma).(11)

The block graph GpG_p is the union of colored Cayley graphs for A=ApA=A_p and C=CpC=C_p, with vertex set Xp=X(Ap,Cp)X_p=X(A_p,C_p) and coloring cp=cc_p=c. The metric block Mp=M(Gp,cp,Dp,Rp)M_p=M(G_p,c_p,D_p,R_p) has distance dpd_p and label ℓp\ell_p from the construction above. Subscripts pp also distinguish its inclusions and vertex anchors. Its distinguished graph vertex is x*=(0,χ0,1)x_*=(0,\chi_0,1), where χ0\chi_0 is the constant zero coloring and 11 is the group identity✦; its base point is the anchor op=αp(ap(x*))o_p=\alpha_p(a_p(x_*)).✦

The Claim

Theorem 1. Let GG be a graph with finite reversible port set PP, finite nonempty color set CC and coloring cc, and let D≥0D\ge0 and R≥1R\ge1 be integers. Form its metric block (M,d)(M,d) and label ℓ\ell as above. For a source vertex x∈Xx\in X and a port e∈Pe\in P, the source edge estimate is (12). The label map satisfies (13) for all points u,v∈Mu,v\in M. d(ι(x),ι(m(x,e)))≤1.d\bigl(\iota(x),\iota(m(x,e))\bigr)\le1.(12)✦ ∥ℓ(u)−ℓ(v)∥∞≤d(u,v).\|\ell(u)-\ell(v)\|_\infty\le d(u,v).(13)✦ The own-color coordinate and vertex anchor satisfy (14) and (15). ℓX(x)(c(x))=0.\ell_X(x)(c(x))=0.(14)✦ d(ι(x),α(a(x)))≤R.d(\iota(x),\alpha(a(x)))\le R.(15)✦ For u,v∈Mu,v\in M with d(u,v)<Rd(u,v)<R, (16) holds. (u,v)∈𝒮d(u,v).(u,v)\in\mathcal S_{d(u,v)}.(16)✦ For an integer 0≤n<R0\le n<R and u∈Mu\in M, write B¯d(u,n)\overline B_d(u,n) for the closed ball of radius nn centered at uu; the local cardinality estimates are (17) and (18). |B¯d(u,n)|≤|𝒲n(P)|.\bigl|\overline B_d(u,n)\bigr|\le|\mathcal W_n(P)|.(17)✦ |supp⁡D(u)|≤|𝒲D(P)|.|\operatorname{supp}_D(u)|\le|\mathcal W_D(P)|.(18)✦

For the block (Mp,dp,op)(M_p,d_p,o_p) at any integer p≥1p\ge1, distinct points u,vu,v satisfy (19), and arbitrary points satisfy (20). 1≤dp(u,v)(u≠v).1\le d_p(u,v)\qquad(u\ne v).(19)✦ dp(u,v)≤Bp.d_p(u,v)\le B_p.(20)✦ The base point bound (21) holds for every source vertex x∈Xpx\in X_p. Rp≤dp(ιp(x),op).R_p\le d_p(\iota_p(x),o_p).(21)✦ Every u∈Mpu\in M_p satisfies the support bound (22). For every finite S⊆MpS\subseteq M_p and j∈Sj\in S, the transition bound is (23). |supp⁡Dp(u)|≤Hp.|\operatorname{supp}_{D_p}(u)|\le H_p.(22)✦ |{k∈S:j⤳Lpk}|≤Qp.\bigl|\{k\in S:j\leadsto_{L_p}k\}\bigr|\le Q_p.(23)✦

In the paper, the result reads: for the preceding construction with p≥1p\ge1, (i) (Mp,dp,op)(M_p,d_p,o_p) is a countably infinite pointed metric space with separation at least one, diameter at most BpB_p, a finite anchor set containing opo_p and every source edge of length at most one; (ii) ℓp\ell_p is 11-Lipschitz for the supremum norm, each source vertex has zero own-color coordinate and its anchor has the same label; (iii) every source vertex xx and anchor bb satisfy dp(ιp(x),αp(b))≥Rpd_p(\iota_p(x),\alpha_p(b))\ge R_p, with dp(ιp(x),αp(ap(x)))=Rpd_p(\iota_p(x),\alpha_p(a_p(x)))=R_p and hence dp(ιp(x),op)≥30pd_p(\iota_p(x),o_p)\ge30p; (iv) every closed ball of radius 2Lp2L_p has at most QpQ_p points and every label has at most HpH_p coordinates below DpD_p.

What Is Checked

The assertions concern the minimum path metric of a colored graph with finite reversible ports and realized label anchors, with integer cap D≥0D\ge0 and attachment scale R≥1R\ge1, and its specialization to the block graphs at integers p≥1p\ge1 with the scales in (9).

For every word ball and generator, an extended generator translation as defined at (10) exists.✦ The block color count kpk_p is positive.✦