OctoInformBeta

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

Section 3 (setting): incidences and the finite replacement for Lemma 3.1: Reversible incidences and short nonbacktracking walks in permutation graphs with all vertex colorings

Colored graph models from free group balls.

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 graph setting for the bounded block in the Lipschitz-free space construction concerns reversible walks and vertex colorings. Its graphs arise from permutation groups of free group word balls, with a separate component for every coloring.

Definition 1. A graph GG with reversible ports on a vertex set XX and port set DD consists of a port reversal r:D→Dr:D\to D and a move map μ:X×D→X\mu:X\times D\to X satisfying (1): r(r(e))=e,μ(μ(x,e),r(e))=x(x∈X,e∈D).r(r(e))=e, \qquad \mu(\mu(x,e),r(e))=x \quad(x\in X,\ e\in D).(1)✦ An incidence is a pair (x,e)∈X×D(x,e)\in X\times D; its incidence reversal is the involutive permutation ι\iota defined by (2): ι:X×D→X×D,ι(x,e)=(μ(x,e),r(e)).\iota:X\times D\longrightarrow X\times D, \qquad \iota(x,e)=(\mu(x,e),r(e)).(2)✦

For a graph GG with reversible ports, the walk endpoint walk⁡G(x,w)\operatorname{walk}_G(x,w) is the vertex reached by following a finite port word ww from xx, as in (3), where ⌀\varnothing denotes the empty word and e::we::w denotes the word obtained by placing ee before ww. A nonbacktracking port word w=(e1,…,em)w=(e_1,\ldots,e_m) for a graph GG with reversible ports, also called a reduced word for GG, is a finite word in its port set satisfying (4). walk⁡G(x,⌀)=x,walk⁡G(x,e::w)=walk⁡G(μ(x,e),w).\operatorname{walk}_G(x,\varnothing)=x, \qquad \operatorname{walk}_G(x,e::w) =\operatorname{walk}_G(\mu(x,e),w).(3)✦ w=(e1,…,em) is reduced⇔ej+1≠r(ej)(1≤j<m).w=(e_1,\ldots,e_m)\text{ is reduced} \quad\Longleftrightarrow\quad e_{j+1}\ne r(e_j)\quad(1\le j<m).(4)✦

Word Ball Permutation Models

Let AA be a generator set and let FAF_A denote the free group on AA, with canonical generators uau_a. The free group word ball WNW_N in FAF_A is the set of elements of reduced word length at most the nonnegative integer NN; the word ball permutation group HNH_N is the group of permutations of WNW_N, as in (5). WN={g∈FA:|g|≤N},HN=Sym⁡(WN).W_N=\{g\in F_A:|g|\le N\}, \qquad H_N=\operatorname{Sym}(W_N).(5) An extended generator translation σN,a\sigma_{N,a} is a chosen permutation of WNW_N agreeing with left multiplication by uau_a wherever that multiplication stays in WNW_N, as specified in (6).✦ σN,a(g)=uagif g∈WN and |uag|≤N.\sigma_{N,a}(g)=u_ag \quad\text{if }g\in W_N\text{ and }|u_ag|\le N.(6) The word ball permutation representation ρN:FA→HN\rho_N:F_A\to H_N is the homomorphism extending these generator assignments in (7).✦ ρN(ua)=σN,a(a∈A).\rho_N(u_a)=\sigma_{N,a}\quad(a\in A).(7)

The signed port set DD is the set A×{+1,−1}A\times\{+1,-1\}. Port reversal changes the sign✦, and the signed generator associated with a port is the corresponding generator or its inverse, as in (8).✦ r(a,ε)=(a,−ε),ℓ(a,ε)=uaε.r(a,\varepsilon)=(a,-\varepsilon), \qquad \ell(a,\varepsilon)=u_a^{\varepsilon}.(8) The Cayley graph GNG_N is the graph with reversible ports on HNH_N whose move map is given in (9), with the reversal from (8).✦ μN(x,e)=xρN(ℓ(e))(x∈HN,e∈D).\mu_N(x,e)=x\rho_N(\ell(e)) \quad(x\in H_N,\ e\in D).(9)

The Claim

Let CC be a color set. A coloring of HNH_N is a function c:HN→Cc:H_N\to C.

Definition 2. The all-colorings graph at radius NN is the graph with reversible ports whose vertex set is (HN→C)×HN(H_N\to C)\times H_N, whose port set is DD, and whose move and reversal are given in (10): μ̃N((c,x),e)=(c,μN(x,e)),r̃(e)=r(e).\widetilde\mu_N((c,x),e)=(c,\mu_N(x,e)), \qquad \widetilde r(e)=r(e).(10)✦ The vertex set VV of the union of colored Cayley graphs is the disjoint union in (11): V=∐N≥0((HN→C)×HN).V=\coprod_{N\ge0}\bigl((H_N\to C)\times H_N\bigr).(11)✦ The union of colored Cayley graphs is the graph with reversible ports on VV defined by (12): μV((N,c,x),e)=(N,μ̃N((c,x),e)),rV(e)=r(e).\mu_V((N,c,x),e)=(N,\widetilde\mu_N((c,x),e)), \qquad r_V(e)=r(e).(12)✦ The componentwise coloring γ:V→C\gamma:V\to C of the union of colored Cayley graphs is the function that evaluates each coloring at its group coordinate, as in (13): γ(N,c,x)=c(x).\gamma(N,c,x)=c(x).(13)✦

Theorem 1. Let N≥0N\ge0, let x∈HNx\in H_N, and let w=(e1,…,em)w=(e_1,\ldots,e_m) be a reduced port word for GNG_N of length m≤Nm\le N. The prefix endpoint map in (14) is injective: {0,…,m}→HN,i↦walk⁡GN(x,(e1,…,ei)).\{0,\ldots,m\}\longrightarrow H_N, \qquad i\longmapsto\operatorname{walk}_{G_N}(x,(e_1,\ldots,e_i)).(14)✦

In the paper, the result reads: for every even degree Δ≥4\Delta\ge4 and positive number kk of colors, there is a deterministic sequence of finite nonempty kk-colored Δ\Delta-regular multigraphs, with oriented incidences paired by reversal and two distinct incidences for each loop, such that every fixed induced rooted colored ball frequency converges to its frequency in the independently uniformly colored Δ\Delta-regular tree, where a nonbacktracking walk never immediately reverses its preceding incidence.

What Is Checked

The constructions are stated over generator and color sets AA and CC, the word ball permutation groups HNH_N, and the signed ports DD; the prefix endpoint assertion assumes a reduced word of length at most NN. For every radius NN and generator aa, an extended generator translation satisfying (6) exists.✦