OctoInformBeta

OpenAI preprint, September 2026 · §5. Conditioned trees and uniform path sums · §5

Lemma 5.6 [Common ancestors and walk minima]: Bounds on intervening route lengths within maximum core degree and a real-distance error bound between pole darts for uniformly approximating walks

Common route bounds and distance comparison on core trees.

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

In the block-core decomposition of rooted Fortuin-Kasteleyn planar maps with n+1n + 1 edges, encoded by a Galton-Watson tree conditioned on size N=2n+1N = 2n + 1 with exploration walk WjW_j, graph distances between corners are governed by increments of WjW_j along tree paths. Given two nodes visited in preorder, how does the path length to their lowest common ancestor constrain the path lengths of nodes visited between them, and how closely does the walk increment from an intervening minimum approximate the real graph distance between their poles?

Chord Graphs and Two-stack Matchings

For a natural number KK, the set of chord opening endpoints Op⁡(π)\operatorname{Op}(\pi) of a permutation π\pi of {0,…,K−1}\{0, \dots, K - 1\} is the subset of {0,…,K−1}\{0, \dots, K - 1\} consisting of all indices ii satisfying i<π(i)i < \pi(i), and each such index is a chord opening endpoint of π\pi.✦ The chord crossing relation on the chord opening endpoints Op⁡(π)\operatorname{Op}(\pi) of a permutation π\pi of {0,…,K−1}\{0, \dots, K - 1\} is the relation holding between two chord opening endpoints x,y∈Op⁡(π)x, y \in \operatorname{Op}(\pi) whenever either x<y<π(x)<π(y)x < y < \pi(x) < \pi(y) or y<x<π(y)<π(x)y < x < \pi(y) < \pi(x).✦ The chord intersection graph Gch(π)G_{\mathrm{ch}}(\pi) of a permutation π\pi on {0,…,K−1}\{0, \dots, K - 1\} is the simple graph on Op⁡(π)\operatorname{Op}(\pi) whose edges are the pairs of chord opening endpoints satisfying the chord crossing relation.✦

The alphabet ℒ\mathcal{L} of typed burger-order letters consists of burger tokens and order tokens each carrying a Boolean type in Bool\mathrm{Bool} (true\mathrm{true} or false\mathrm{false}).✦ The typed word stack execution of a list ww of typed burger-order letters from a freshest-first stack ss of Boolean types is the evaluation of ww step by step starting from ss, returning either a final stack of Boolean types or failure on an illegal closure.

A non-crossing arch matching EE on a list ℓ\ell in a set SS is a list of ordered pairs in S×SS \times S such that (ℓ,E)(\ell, E) is generated inductively from empty lists by either prepending an unmatched element of SS to ℓ\ell while leaving EE unchanged, or, from non-crossing arch matchings E1E_1 on a list LL and E2E_2 on a list RR, placing a pair (x,y)(x, y) before the concatenation of E1E_1 and E2E_2 to match the concatenation of xx, LL, yy, and RR.✦ The list of endpoints end⁡(E)\operatorname{end}(E) of a list EE of pairs in a set SS is the list in SS obtained by flattening each pair (x,y)(x, y) in EE into xx and yy in order.✦

A two-stack matching certificate M=(E1,E2)M = (E_1, E_2) for a map w:S→ℒw \colon S \to \mathcal{L} along a list ℓ\ell in a set SS is a pair of non-crossing arch matchings E1E_1 and E2E_2 on ℓ\ell such that end⁡(E1‖E2)\operatorname{end}(E_1 \mathbin{\Vert} E_2) (where ‖\mathbin{\Vert} denotes list concatenation) is a permutation of ℓ\ell, every pair (x,y)(x, y) in E1E_1 has w(x)w(x) a burger token of type true\mathrm{true} and w(y)w(y) an order token of type true\mathrm{true}, and every pair (x,y)(x, y) in E2E_2 has w(x)w(x) a burger token of type false\mathrm{false} and w(y)w(y) an order token of type false\mathrm{false}.✦ The arch transposition product τ(E)\tau(E) of a list EE of pairs in a set SS is the permutation of SS defined recursively as the identity on the empty list and as τ(E′)∘(xy)\tau(E') \circ (x\; y) when EE begins with (x,y)(x, y) followed by E′E', where (xy)(x\; y) is the transposition swapping xx and yy.✦ The stack matching mate permutation mate⁡(M)\operatorname{mate}(M) of a two-stack matching certificate M=(E1,E2)M = (E_1, E_2) on SS is the permutation τ(E1‖E2)\tau(E_1 \mathbin{\Vert} E_2) of SS.

A word ww of typed burger-order letters satisfies the connected core word condition if there exist a natural number KK, a map v:{0,…,K−1}→ℒv \colon \{0, \dots, K - 1\} \to \mathcal{L} whose list of values (v(0),…,v(K−1))(v(0), \dots, v(K - 1)) equals ww, and a two-stack matching certificate MM for vv along (0,…,K−1)(0, \dots, K - 1) such that 0∈Op⁡(mate⁡(M))0 \in \operatorname{Op}(\operatorname{mate}(M)) and every element of Op⁡(mate⁡(M))\operatorname{Op}(\operatorname{mate}(M)) is reachable from 00 in Gch(mate⁡(M))G_{\mathrm{ch}}(\operatorname{mate}(M)).✦ A connected typed core cc of length |c||c| is a word of typed burger-order letters satisfying the connected core word condition, and its positions {0,…,|c|−1}\{0, \dots, |c| - 1\} are the corners of cc.✦

Core Trees and Real Graph Distances

An ordered tree of cores tt is an inductive tree that is either a leaf or a branch (c,(ti)0≤i<|c|)(c, (t_i)_{0 \le i < |c|}) consisting of a connected typed core cc and a family of child ordered trees of cores tit_i indexed by the corners i∈{0,…,|c|−1}i \in \{0, \dots, |c| - 1\} of cc.✦ The set of core tree nodes Node⁡(t)\operatorname{Node}(t) of an ordered tree of cores tt consists of a single root node when tt is a leaf, and, when tt is a branch (c,(ti))(c, (t_i)), of the root of tt together with all pairs (i,v)(i, v) where ii is a corner of cc and v∈Node⁡(ti)v \in \operatorname{Node}(t_i).✦ The set of core tree darts Dart⁡(t)\operatorname{Dart}(t) of an ordered tree of cores tt is the empty set when tt is a leaf, and, when tt is a branch (c,(ti))(c, (t_i)), consists of all corners i∈{0,…,|c|−1}i \in \{0, \dots, |c| - 1\} of the root core cc together with all pairs (i,d)(i, d) where ii is a corner of cc and d∈Dart⁡(ti)d \in \operatorname{Dart}(t_i).✦

The core tree dart label λt:Dart⁡(t)→ℒ\lambda_t \colon \operatorname{Dart}(t) \to \mathcal{L} of an ordered tree of cores tt is the map sending a root corner dart ii of a branch (c,(tj))(c, (t_j)) to the ii-th letter of cc and a child dart (i,d)(i, d) to λti(d)\lambda_{t_i}(d).✦ The core tree dart list darts⁡(t)\operatorname{darts}(t) of an ordered tree of cores tt is the empty list if tt is a leaf, and for a branch (c,(tj))(c, (t_j)) is the concatenation over i=0,…,|c|−1i = 0, \dots, |c| - 1 of the root corner dart ii followed by the darts of darts⁡(ti)\operatorname{darts}(t_i) lifted as pairs (i,d)(i, d).✦ The core tree stack matching Mt=(E1(t),E2(t))M_t = (E_1(t), E_2(t)) of an ordered tree of cores tt is a two-stack matching certificate for λt\lambda_t along darts⁡(t)\operatorname{darts}(t).

The preorder node index idx⁡t(v)∈ℕ\operatorname{idx}_t(v) \in \mathbb{N} of a node v∈Node⁡(t)v \in \operatorname{Node}(t) in an ordered tree of cores tt vanishes when tt is a leaf or vv is the root of a branch, and for a child node (i,u)(i, u) of a branch (c,(tj))(c, (t_j)) equals 11 plus the number of nodes in the child subtrees tjt_j for j<ij < i plus idx⁡ti(u)\operatorname{idx}_{t_i}(u).✦ Writing δc(i)∈ℕ\delta_c(i) \in \mathbb{N} for the corner increment of a connected typed core cc at corner i∈{0,…,|c|−1}i \in \{0, \dots, |c| - 1\}, the node route length route⁡t(v)∈ℕ\operatorname{route}_t(v) \in \mathbb{N} of a node v∈Node⁡(t)v \in \operatorname{Node}(t) in an ordered tree of cores tt is 00 when tt is a leaf or vv is the root of a branch, and at a child node (i,u)(i, u) of a branch (c,(tj))(c, (t_j)) is given by route⁡t(i,u)=δc(i)+route⁡ti(u).\operatorname{route}_t(i, u) = \delta_c(i) + \operatorname{route}_{t_i}(u).(1)✦ The common route length common⁡t(v,w)∈ℕ\operatorname{common}_t(v, w) \in \mathbb{N} of two nodes v,w∈Node⁡(t)v, w \in \operatorname{Node}(t) in an ordered tree of cores tt is 00 when tt is a leaf, when either vv or ww is the root of a branch, or when vv and ww lie in distinct child subtrees of a branch, and for two nodes (i,v′)(i, v') and (i,w′)(i, w') in the same child subtree tit_i of a branch (c,(tj))(c, (t_j)) is given by common⁡t((i,v′),(i,w′))=δc(i)+common⁡ti(v′,w′).\operatorname{common}_t((i, v'), (i, w')) = \delta_c(i) + \operatorname{common}_{t_i}(v', w').(2)✦

The maximum core degree Δ(t)∈ℕ\Delta(t) \in \mathbb{N} of an ordered tree of cores tt is 00 when tt is a leaf, and for a branch (c,(ti))(c, (t_i)) is given by Δ(t)=max⁡(|c|,max0≤i<|c|Δ(ti)).\Delta(t) = \max\Bigl(|c|, \max_{0 \le i < |c|} \Delta(t_i)\Bigr).(3)✦

The node pole dart pole⁡t(v)\operatorname{pole}_t(v) of a node v∈Node⁡(t)v \in \operatorname{Node}(t) in an ordered tree of cores tt is either a dart in Dart⁡(t)\operatorname{Dart}(t) or undefined: a leaf node has no pole dart, the root of a branch (c,(ti))(c, (t_i)) has the entry corner dart 00 of cc, and a child node (i,u)(i, u) in tit_i has (i,pole⁡ti(u))(i, \operatorname{pole}_{t_i}(u)) if pole⁡ti(u)\operatorname{pole}_{t_i}(u) is defined and otherwise the next corner dart of cc after ii under the cyclic shift.✦

For a permutation ρ\rho of a set SS, the cycle vertex set V(ρ)V(\rho) is the set of cycle equivalence classes of SS under ρ\rho✦, and the cycle vertex projection πρ:S→V(ρ)\pi_\rho \colon S \to V(\rho) is the map sending each d∈Sd \in S to its cycle class in V(ρ)V(\rho).✦ Given an edge permutation σ\sigma and a vertex rotation ρ\rho on a set SS, the permutation wedge dart graph G(σ,ρ)G(\sigma, \rho) is the simple graph on V(ρ)V(\rho) in which two distinct vertices x,y∈V(ρ)x, y \in V(\rho) are adjacent whenever there exists d∈Sd \in S with {πρ(d),πρ(σ(d))}={x,y}\{\pi_\rho(d), \pi_\rho(\sigma(d))\} = \{x, y\}.✦ On an ordered tree of cores tt with stack matching Mt=(E1(t),E2(t))M_t = (E_1(t), E_2(t)), set st=σlist(t)∘τ(E1(t))s_t = \sigma_{\mathrm{list}}(t) \circ \tau(E_1(t)), where σlist(t)\sigma_{\mathrm{list}}(t) is the permutation of Dart⁡(t)\operatorname{Dart}(t) formed from darts⁡(t)\operatorname{darts}(t); writing dist⁡G(x,y)\operatorname{dist}_G(x, y) for graph distance in a simple graph GG, the real graph distance dt(a,b)∈ℝd_t(a, b) \in \mathbb{R} between two darts a,b∈Dart⁡(t)a, b \in \operatorname{Dart}(t) is defined by dt(a,b)=dist⁡G(mate⁡(Mt),st)(πst(a),πst(b)).d_t(a, b) = \operatorname{dist}_{G(\operatorname{mate}(M_t), s_t)}(\pi_{s_t}(a), \pi_{s_t}(b)).(4)✦

The Claim

Theorem 1. Let tt be an ordered tree of cores.

  1. If v,u,w∈Node⁡(t)v, u, w \in \operatorname{Node}(t) satisfy idx⁡t(v)≤idx⁡t(u)≤idx⁡t(w)\operatorname{idx}_t(v) \le \operatorname{idx}_t(u) \le \operatorname{idx}_t(w), then common⁡t(v,w)≤route⁡t(u).\operatorname{common}_t(v, w) \le \operatorname{route}_t(u).(5)✦

  2. If v,w∈Node⁡(t)v, w \in \operatorname{Node}(t) satisfy idx⁡t(v)≤idx⁡t(w)\operatorname{idx}_t(v) \le \operatorname{idx}_t(w), then there exists a node u∈Node⁡(t)u \in \operatorname{Node}(t) with idx⁡t(v)≤idx⁡t(u)≤idx⁡t(w)\operatorname{idx}_t(v) \le \operatorname{idx}_t(u) \le \operatorname{idx}_t(w) such that route⁡t(u)≤common⁡t(v,w)+Δ(t).\operatorname{route}_t(u) \le \operatorname{common}_t(v, w) + \Delta(t).(6)✦

  3. Let v,m,w∈Node⁡(t)v, m, w \in \operatorname{Node}(t) satisfy idx⁡t(v)≤idx⁡t(m)≤idx⁡t(w)\operatorname{idx}_t(v) \le \operatorname{idx}_t(m) \le \operatorname{idx}_t(w), and let a,b∈Dart⁡(t)a, b \in \operatorname{Dart}(t) satisfy pole⁡t(v)=a\operatorname{pole}_t(v) = a and pole⁡t(w)=b\operatorname{pole}_t(w) = b. Suppose W:Node⁡(t)→ℝW \colon \operatorname{Node}(t) \to \mathbb{R} is a function and α≥0\alpha \ge 0 and ε\varepsilon are real numbers such that |route⁡t(u)−αW(u)|≤ε|\operatorname{route}_t(u) - \alpha W(u)| \le \varepsilon for every u∈Node⁡(t)u \in \operatorname{Node}(t), and W(m)≤W(u)W(m) \le W(u) for every u∈Node⁡(t)u \in \operatorname{Node}(t) satisfying idx⁡t(v)≤idx⁡t(u)≤idx⁡t(w)\operatorname{idx}_t(v) \le \operatorname{idx}_t(u) \le \operatorname{idx}_t(w). Then |dt(a,b)−α(W(v)+W(w)−2W(m))|≤4Δ(t)+4ε.|d_t(a, b) - \alpha(W(v) + W(w) - 2W(m))| \le 4\Delta(t) + 4\varepsilon.(7)✦

In the paper, the result reads: if j≤j′j \le j' and v*v_* is the lowest common ancestor of the nodes vjv_j and vj′v_{j'}, then W(v*)≤min⁡j≤r≤j′Wr≤W(v*)+ΔNW(v_*) \le \min_{j \le r \le j'} W_r \le W(v_*) + \Delta_N, where WW stands for the exploration walk (with Wr=W(vr)W_r = W(v_r)) and Δ(t)\Delta(t) stands for ΔN\Delta_N.

What Is Checked

The bounds (5) and (6) are stated over any ordered tree of cores tt and nodes ordered by preorder node index (v,u,w∈Node⁡(t)v, u, w \in \operatorname{Node}(t) with idx⁡t(v)≤idx⁡t(u)≤idx⁡t(w)\operatorname{idx}_t(v) \le \operatorname{idx}_t(u) \le \operatorname{idx}_t(w) for the intervening route lower bound (5), and v,w∈Node⁡(t)v, w \in \operatorname{Node}(t) with idx⁡t(v)≤idx⁡t(w)\operatorname{idx}_t(v) \le \operatorname{idx}_t(w) for the low intervening node bound (6)). The pole distance walk comparison (7) is stated over any tt, nodes v,m,w∈Node⁡(t)v, m, w \in \operatorname{Node}(t) with idx⁡t(v)≤idx⁡t(m)≤idx⁡t(w)\operatorname{idx}_t(v) \le \operatorname{idx}_t(m) \le \operatorname{idx}_t(w), pole darts a,b∈Dart⁡(t)a, b \in \operatorname{Dart}(t) of vv and ww, an arbitrary function W:Node⁡(t)→ℝW \colon \operatorname{Node}(t) \to \mathbb{R}, and real numbers α≥0\alpha \ge 0 and ε\varepsilon satisfying uniform route-length approximation and local minimality of WW at mm.

Whenever the list of values obtained by applying a map w:S→ℒw \colon S \to \mathcal{L} along a list ℓ\ell in a set SS has its typed word stack execution from an empty stack terminate in an empty stack, there exists a two-stack matching certificate for ww along ℓ\ell.✦ For every ordered tree of cores tt, the dart-label sequence along darts⁡(t)\operatorname{darts}(t) reduces an empty stack to an empty stack under typed word stack execution, providing the core tree stack matching MtM_t. On chord opening endpoints of a permutation, the chord crossing relation is symmetric and irreflexive.