结果族 089：Bounded-distortion L1 embeddings of planar and bounded-treewidth graphs · 学科：Convex and metric geometry · 验证状态：主结果已 Lean 形式化
一张大网络如果能拆成一串”小袋子”——每个袋只装少量节点、袋子沿一棵树相连——就说它树宽有界。论文证明：凡树宽有界的网络，无论多大、边长多离谱，其最短路距离都能嵌进棋盘距离（@@M@@L^1@@），误差倍数只依赖树宽，与网络规模无关。这解决了 GNRS 嵌入猜想的有界树宽情形。
关键词卡片
@@M@@C_k@@。看个具体例子
一条”三角形串”：三角形 @@M@@(a,b,c)@@ 与三角形 @@M@@(c,d,e)@@ 共享顶点 @@M@@c@@。它的树分解只需两个袋：@@M@@\{a,b,c\}@@ 与 @@M@@\{c,d,e\}@@，袋大小 3，树宽 2。
定理代入：凡有袋大小至多 @@M@@k@@ 的树分解的图，对任意正实数边长，存在映射 @@M@@F@@ 使 @@M@@d_G(u,v)\le\|F(u)-F(v)\|_1\le C_k\,d_G(u,v)@@，且 @@M@@C_k@@ 与顶点数、边长比例全都无关。由 Robertson–Seymour 定理，凡禁用任一固定平面子式的图族自动获得一致失真界。
为什么值得关心
它补上了 GNRS 猜想的另一块试验田（平面情形由姊妹篇解决）：证明直接在树分解上构造割测度，”袋内状态有限”使误差不随分解深度累积，并连带给出流—割间隙与近似算法的推论。
已 Lean 形式化
第一级台阶
导读的”袋子”是理解本文的钥匙：一张大网络若能装进一串小袋——每袋只放少量节点、相邻袋共享少许节点、袋子本身连成一棵树——就说它离树不远。对象就是这类网络，每条边带任意长度，两点的距离仍是沿边走的最短总长。要做的事与姊妹篇相同：给每个节点发一份”棋盘坐标”，使棋盘路程与真实路程互差固定倍数；不同在于这里的倍数只许依赖袋子大小，与网络多大、边长多悬殊、分解多深全都无关。
第二级台阶
| 用本科术语精确化：树分解把图装进袋族 {B_t}，要求袋覆盖全部顶点、每条边的两端同在某袋、每个顶点所属的袋构成连通子树；树宽是袋子大小的最大值减一。失真仍指经缩放后 d_G(u,v)≤‖F(u)−F(v)‖₁≤C·d_G(u,v)。结构工具是：有限 L¹ 伪度量恰为割伪度量 δ_S(u,v)= | 1_S(u)−1_S(v) | 的非负组合——找嵌入等价于找一族带权割，边只被收常数倍边长的割费，而每对顶点被按比例分开。 |
第三级台阶
定理的语境是 GNRS 猜想的有界树宽情形：对每个袋大小上界 k 存在常数 C_k，凡有袋至多 k 的树分解的有限连通图、任意正实边长，都能以失真 C_k 嵌入（甚至有限维）L¹；常数与顶点数、分解深度、边长比例无关，但证明只给存在性、无对 k 的显式估计。袋大小有界挡住的是状态空间：袋上二进赋值至多 2^k 种、弱序至多 k! 种，一切组合计数都只看 k。证明在树分解上直接定义割测度：相邻袋的”袋割律”一致即可马尔可夫粘合成全局割，上界自动；下界靠粒子更新保律、预留传输不确定度，最后以紧性论证收口。由 Robertson–Seymour 定理，一切禁用固定平面子式的图族随之获得一致界。
证明了对每个固定的树宽（treewidth）上界，所有允许任意正实数边长的有限连通图都以仅依赖树宽的常数失真（distortion）嵌入 @@M@@L_1@@，肯定解决 Gupta–Newman–Rabinovich–Sinclair 猜想的有界树宽情形；由 Robertson–Seymour 定理，一切禁用固定平面子式的图族同时获得一致界。
树分解（tree decomposition）把图 @@M@@G=(V,E)@@ 装进一棵树：每个节点附一个顶点子集（袋，bag），袋覆盖所有顶点与边，且每个顶点所属的袋构成连通子树；树宽是 @@M@@\max_t|B_t|-1@@ 的最小值。有界树宽与平面性并列，是 GNRS 猜想（”每个真禁用子式闭图族一致嵌入 @@M@@L_1@@“）的两大试验场之一。此前进展各有缺口：树宽 2（系列平行图）的常数失真已知且最优值为 2；Lee–Sidiropoulos 用随机嵌入支配树解决有界路径宽（pathwidth），Abraham–Filtser–Gupta–Neiman 改进到 @@M@@O(\sqrt p)@@；但这条路线对一般树宽原理上走不通——某些系列平行度量嵌入树的期望失真为 @@M@@\Omega(\log n)@@。最接近的先驱是 Chlamtáč–Krauthgamer–Raghavendra 的局部一致性定理：它要求任意 @@M@@t+3@@ 个点的限制存在彼此一致的等距割表示，而本文设法丢掉了这一假设。Filtser 等的填充分解（padded decomposition）提供随机分区输入，却也只给出 @@M@@O(\sqrt{\log(2+t)\log n})@@ 的依赖顶点数的界。障碍在于：局部扰动带来的好处不能随尺度数或分解深度累积流失。
主定理：对每个整数 @@M@@k\ge 2@@ 存在有限常数 @@M@@C_k\ge 1@@，使得凡具有袋大小至多 @@M@@k@@ 的树分解的有限连通图，对任意边长 @@M@@\ell:E\to(0,\infty)@@，都有映射 @@M@@F@@ 进入实 @@M@@L_1@@（可取有限维 @@M@@\ell_1@@）满足
@@M@@Dd_{G,\ell}(u,v)\le\|F(u)-F(v)\|_1\le C_k\,d_{G,\ell}(u,v)\qquad(u,v\in V).@@
常数与顶点数、分解深度、边长比例全部无关；证明只给出 @@M@@C_k@@ 的存在性，不含对 @@M@@k@@ 的显式估计。三项推论：其一，多商品流的流—割间隙满足 @@M@@\lambda_*\le\phi_*\le C_k\lambda_*@@（最小化 @@M@@\phi_*@@ 即非均匀最稀疏割问题）；其二，由 Robertson–Seymour 的禁用平面子式定理，排除任一固定平面子式的图族获得一致失真界；其三，结合 Gupta–Talwar–Witmer 与 Cohen-Addad–Mömke–Verdugo 的近似算法，对正有理边长可在固定参数可解（FPT）时间内算出失真至多 @@M@@(2+\varepsilon)C_k@@ 的嵌入。
构造直接在树分解上定义割测度，允许任意分支结构，分四步。
第一步：袋割律与马尔可夫粘合（Markov gluing）。 给每个袋 @@M@@B@@ 的二进制赋值空间 @@M@@\{0,1\}^B@@ 赋非负质量，称为袋割律；相邻袋的律在交集上的限制一致（consistent）时，可沿分解树逐袋条件采样粘合成全局割测度 @@M@@\rho_\mu@@，其显式公式为袋质量之积除以交集质量之积。只要每条边在其袋内的分离质量不超过 @@M@@U\ell(uv)@@，沿最短路用三角不等式即得全局上界 @@M@@D_\mu\le U\,d@@。但一致性本身给不出远处袋中顶点对的下界——这是全文难点所在。
第二步：粒子更新保持袋律。 粒子（particle）是顶点上的实函数，对它做阈值扫掠（threshold sweep）产生割测度，分离量恰为 @@M@@|F(u)-F(v)|@@。核心更新：把当前袋上弱序相同的两个粒子换成 @@M@@f+g@@ 与 @@M@@f-g@@，其中扰动 @@M@@g@@ 在该袋上为零——由于连续阈值质量是高度值的仿射函数，袋上的割律不变，却允许向子袋发散出不同的延续。一个二次型数值不变量保证无论更新多少次，所有粒子的 Lipschitz 常数都一致有界。
第三步：预留与不确定性传输。 预留（reservation）冻结一对粒子；袋上至多 @@M@@k!@@ 种序，鸽笼原理保证足够长的粒子表中总有两个未预留粒子同序可用。预留对 @@M@@f\pm g@@ 沿袋路径构成每个袋律的公共子测度，而在远端点 @@M@@z@@ 处两函数值相差 @@M@@2|g(z)|@@——这正是”不确定性” @@M@@E_\nu(z\mid P)@@：固定测试袋赋值后，@@M@@z@@ 的标签中不可预测的那部分质量。核心传输命题断言 @@M@@D_\mu(y,z)\ge b_k\,E_\nu(z\mid P)@@：证明把测试袋的完整赋值插入一条每层至多 @@M@@2^k@@ 个状态的对称马尔可夫链，再引用 CKR 的对称马尔可夫流定理，损失 @@M@@C(2^k)@@ 只依赖 @@M@@k@@，与袋的个数无关。
第四步：两套日程与紧性下界。 @@M@@D_{\mathrm{bag}}@@ 用每袋有界的二进尺度分离同袋点对，预留沿尺度保持相关的连续袋进行；@@M@@D_{\mathrm{anc}}@@ 以锚（anchor，即发射袋）组织，每条下降路径只保留有界的锚表，保护”当前袋到旧锚距离骤降”之后的条目。若两者之和 @@M@@D@@ 无一致下界，则经非主超滤子取极限，归一化一列分离很差的点对，沿下降路径选出”最年轻”的幸存预留；其扰动包含”到发射袋距离的随机倍数”与”端点附近局部噪声”两个独立部分，迫使每个仍在一定距离处的测试袋内出现点对 @@M@@p,q@@，其距离介于端点到测试袋、到发射袋距离的固定倍数之间，否则噪声制造高度差、经不确定性传输直接产生分离；再用该袋内距离通过锚表规则保护一个更年轻的继任者，与最年轻性矛盾。由此得 @@M@@\lambda_k>0@@ 只依赖 @@M@@k@@。最后把两个割伪度量之和展开为割权 @@M@@w_A@@，映射 @@M@@F(v)=(\lambda_k^{-1}w_A\mathbf 1_A(v))_A@@ 落在有限维 @@M@@\ell_1@@ 中，@@M@@C_k=(U_{\mathrm{bag}}+U)/\lambda_k@@。
主定理已通过 Lean 形式化验证（见结果族 089 的 Lean 文档）。证明引用两项已发表的外部输入：CKR 的马尔可夫粘合原理与对称马尔可夫流定理、Filtser 等的填充分解定理；下界由超滤子紧性论证得到，故 @@M@@C_k@@ 只有存在性、无显式数值估计。本文与平面姊妹篇互相支撑：两者经 1-和拼接与 Lee–Sidiropoulos 约化共同给出几乎可嵌入族的一致界；沿更大完全子图的 clique-sum 闭包仍未建立，完整 GNRS 猜想保持开放。按 OpenAI 官方声明，未经形式化的结果可能存在问题；本文主结果已形式化。
问 1：证明最关键、最脆弱的一步在哪？
答：下界的紧性论证。反设两套日程之和 D 无一致下界，经非主超滤子归一化一列分离很差的点对，沿下降路径选出”最年轻”的幸存预留；其扰动含”到发射袋距离的随机倍数”与”端点局部噪声”两个独立部分，迫使每个仍在一定距离处的测试袋内出现距离适中的点对 p,q，否则噪声制造高度差、经不确定性传输直接分离；再用袋内距离经锚表规则保护一个更年轻的继任者，与最年轻性矛盾。这是全文逻辑最长、工具最非常规的一环。
问 2：与最接近的先驱 CKR 相比，新意是什么？
答：Chlamtáč–Krauthgamer–Raghavendra 的局部一致性定理要求任意 t+3 个点的限制存在彼此一致的等距割表示——这是很强的局部输入。本文直接构造袋割律并证明分离，完全丢掉该假设；CKR 只留下两项技术遗产被引用：马尔可夫粘合与对称马尔可夫流定理。此外，支配树路线（Lee–Sidiropoulos 路径宽方法）对一般树宽原理上走不通——某些系列平行度量嵌入树的期望失真为 Ω(log n)——本文允许任意分支的直接割构造绕开了这一死路。
问 3：哪个假设最不能去掉？
答：袋大小有界不只是复杂度假设，而是每个环节的承重墙：赋值空间 2^k、弱序 k!、每袋活跃二进尺度数、锚表长度、填充分解参数全部由 k 控制。若 k 随图增长，粘合损失与粒子 Lipschitz 界都会失守。注意定理对”深度”无限制——误差不随分解深度累积正是难点所在。
问 4：C_k 连显式估计都没有，这算什么水平的定理？
答：存在性证明。下界常数 λ_k 来自超滤子紧性论证，本质上是反证法产物，不给出数值；C_k=(U_bag+U)/λ_k 因此只有存在性。与树宽 2 情形的最优值 2 相比，本文常数对 k 的增长完全未知。对理论问题（GNRS 情形是否成立）这已足够，对算法应用则偏弱——好在 FPT 近似算法给出失真 (2+ε)C_k 的可计算版本，只是同样不知道绝对数值。
问 5：作为 AI 生成证明，最可能出什么错？
答：混合型工具的接口处：二次型数值不变量要保证任意多次更新后一切粒子一致 Lipschitz；鸽笼原理要求粒子表足够长以躲开至多 k! 种序；超滤子极限要保留有界多个预留。这类”组合＋逻辑＋概率”三栖论证是生成式证明的高危区。主定理已 Lean 形式化，是主要安全网；形式化范围外的推论拼接（几乎可嵌入族）仍需对照原文。
问 6：谁会用这个结果？
答：三路用户：流—割社区经 LLR/AR 对偶得到 λ≤φ≤C_k λ*（非均匀最稀疏割的一致近似）；参数化算法社区经 Gupta–Talwar–Witmer 与 Cohen-Addad–Mömke–Verdugo 得到 FPT 时间内的嵌入计算；图子式结构社区经 Robertson–Seymour 把一切禁用固定平面子式族收入囊中。沿更大完全子图的 clique-sum 闭包仍未建立，完整 GNRS 猜想保持开放。
总评
GNRS 猜想两大试验田之一的收官，方法（袋律粘合＋粒子保律＋不确定性传输）是真正的概念创新且有形式化背书；最大短板是常数存在性而非显式、以及紧性论证的非常规性带来的复核成本。