结果族 131：Rapid mixing of graph switches for every degree sequence · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
想象洗一副牌，但规定每种牌的数量固定，只许”两两对调”。图的版本是：所有顶点的朋友数（度数）不许变，每步随机挑 4 个顶点、把两条边重新配对——这样乱洗下去，多久才能洗”匀”？本文证明：最多 @@M@@2n^8@@ 步一定洗匀，而且对任何度序列都成立，解决了 1999 年提出的 Kannan–Tetali–Vempala 猜想。
关键词卡片
@@M@@(3,2,2,1)@@。@@M@@1/4@@。看个具体例子
一步”交换”长这样：
具体数字：@@M@@n=50@@ 个顶点时，上界 @@M@@2n^8\approx 7.8\times10^{13}@@ 步——巨大，但关键是它只是 @@M@@n@@ 的多项式。此前快速混合只在正则图、P-稳定族等特殊情形成立，对单个度序列毫无附加假设的简单无向情形悬置二十余年；本文补上 @@M@@t_{\mathrm{mix}}\le 2n^8@@，并附赠一个期望多项式比特时间的精确均匀采样算法。
为什么值得关心
在”度数固定”的随机图上均匀采样是网络科学的标准零模型；交换链快速混合意味着”简单乱洗”本身就是理论上可靠的均匀采样器。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读里”每种牌数量固定、只许两两对调的洗牌”翻译过来：对象是一堆共享同一份”朋友数清单”的图，操作是随机挑两条边、在四个端点上重新配对——每个顶点的朋友数一个不增不减；问题是像这样乱洗多少步之后，落在每个图上的概率才几乎相同。洗牌论里”洗匀要多久”在此即混合时间问题。
第二级台阶
本科术语化：度序列 @@M@@d=(d_1,\dots,d_n)@@ 称可图化，指存在简单无向图恰好实现它；@@M@@\Omega_d@@ 是全部这样的图，@@M@@\pi_d@@ 是其上均匀分布。惰性交换链 @@M@@P_d@@：以 @@M@@1/2@@ 概率不动，否则均匀取四元顶点集并在其上均匀取一对完美匹配，若一者在图里另一者不在则替换。衡量”洗匀程度”用总变差距离，混合时间 @@M@@t_{\mathrm{mix}}(d)@@ 定义为距离首次降到 @@M@@1/4@@ 的步数。
第三级台阶
定理的语境：对每个 @@M@@n\ge4@@ 与每个可图化 @@M@@d@@，@@M@@t_{\mathrm{mix}}(d)\le2n^8@@，且谱隙至少 @@M@@[24n^2\binom n4]^{-1}@@。”单个度向量可图化”是唯一假设——它挡住了此前正则、P-稳定等族级限制；惰性约定挡住周期性麻烦。结论即 Kannan–Tetali–Vempala 猜想的简单无向形式：无需任何附加条件，简单乱洗本身就是多项式时间的均匀采样器；推论还由此造出期望多项式比特时间的精确均匀采样算法。
本文证明了简单无向图情形的 Kannan–Tetali–Vempala 猜想：对每个可图化度序列，惰性交换链的总变差混合时间不超过 @@M@@2n^8@@；同时给出期望多项式比特时间的精确均匀采样算法。
给定度序列（degree sequence）@@M@@d=(d_1,\dots,d_n)@@，如何在所有恰好实现它的简单图上均匀采样？这是网络研究中基本零模型（null model）与近似计数的核心问题。Kannan、Tetali、Vempala 于 1999 年在正则二部情形的工作中提出了交换链（switch chain）纲领：每次操作删去两条边，并在四个端点上改放另一种完美匹配，从而保持全部顶点度数；他们猜想这类链对一切可实现的度规范都快速混合（rapid mixing）。此后，正则无向情形由 Cooper–Dyer–Greenhill 解决，Greenhill–Sfragara 等处理了带定量限制的不正则度，Erdős 等人证明了对所有 P-稳定（P-stable）度序列族的快速混合，二部情形最近由 Fu–Qin–Wang 证明。但对单个度序列不作任何额外假设的简单无向情形长期悬而未决——本文正面解决。
论文有两条主结果。其一（定理 1.1）：设 @@M@@n\ge4@@，@@M@@d@@ 可图化（graphical），@@M@@\Omega_d@@ 为度向量等于 @@M@@d@@ 的简单无向图全体。考虑惰性链：以 @@M@@1/2@@ 概率不动；否则均匀取四元顶点集 @@M@@S@@，再均匀取 @@M@@S@@ 上完全图六对有序完美匹配 @@M@@(F,F')@@ 中的一对，若 @@M@@F@@ 的两边都在且 @@M@@F'@@ 的两边都不在就换成 @@M@@F'@@。则在总变差距离（total variation distance）@@M@@1/4@@ 处，混合时间 @@M@@t_{\mathrm{mix}}(d)\le 2n^8@@；若 @@M@@|\Omega_d|>1@@，谱隙（spectral gap）至少为 @@M@@[24n^2\binom n4]^{-1}@@。其二（推论 1.2，精确采样）：存在随机算法，输入任意可图化标长度向量，使用无偏随机比特，几乎必然终止，输出恰按均匀分布取自 @@M@@\Omega_d@@ 的图，期望比特运行时间被输入编码长度的固定多项式界住。
证明不直接分析交换链，而是分析更强的”对重采样”（pair resampling）算子。取顶点对 @@M@@a=\{i,j\}@@，固定其余一切邻接关系，只重新随机分配每个恰与 @@M@@a@@ 一端相邻的”单邻点”（singleton）归哪一端；每条 @@M@@a@@-纤维等距于固定尺寸的均匀子集切片（subset slice）。令 @@M@@E_a@@ 为关于该划分的条件期望投影，@@M@@h_a=I-E_a@@，@@M@@H=\sum_a h_a@@。核心是二次型不等式 @@M@@H^2\succeq H@@。先按 Caputo 的平方生成元方法（squared-generator method）展开 @@M@@H^2=\sum_T H_T^2-(n-3)H+D@@，按两个指标对是否相交分组。相交项归结为固定行、列和的三行 0-1 矩阵上的方差不等式：三个行函数之和的方差至多为各行方差之和的两倍；其证明分两层——块大小固定时用标签对换算子的谱分解控制（思路源自 Carlen–Lieb–Loss 的对称群热流），块计数随机时用 Fu–Qin–Wang 的相邻总量耦合把算子范数压到 @@M@@2@@。不相交项 @@M@@D@@ 是真正的难点：无向图上不相连的对交换会相互依赖，单个交叉项可为负。论文证明固定公共数据后这种依赖的秩至多为一，其负贡献由”两个邻居获得同一端点”的中心化指示投影控制；再用一条切片上的投影比较引理（借助 Johnson 切片分解的低次部分），证明这些投影之和被同切片的对换能量控制，求和后负项成对相消，故 @@M@@D@@ 半正定。合起来得 @@M@@H^2\succeq H@@。随后用带确定性平局判决的 Havel 型论证证明交换链连通，从而 @@M@@H@@ 的核恰为常数，得到 Poincaré 不等式 @@M@@\operatorname{Var}_{\pi_d}(f)\le\langle f,Hf\rangle@@。最后把整条纤维的重采样与纤维内两个单邻点的交换作热浴比较（heat-bath comparison），得 @@M@@H\preceq 2n^2L@@（@@M@@L@@ 为交换图 Laplacian）；结合 @@M@@I-P_d=L/(12\binom n4)@@ 与 @@M@@|\Omega_d|\le 2^{\binom n2}@@，收尾得到 @@M@@2n^8@@。精确采样则用稀有残余混合（rare residual mixture）技巧：取极小 @@M@@\delta=2^{-D}@@ 使 @@M@@(1-\delta)p\le\pi_d@@ 逐点成立，以 @@M@@1-\delta@@ 概率走 @@M@@t@@ 步输出近似分布 @@M@@p@@，以 @@M@@\delta@@ 概率枚举全空间、按整数权重 @@M@@w_G@@ 精确补偏；@@M@@\delta@@ 取得足够小，使枚举的指数成本在期望中被打平，而链达到所需精度只需多项式步数，故期望比特时间仍为多项式。
任务元数据标记本篇为未形式化，暂无 Lean 形式化证明，请以社区核验为准；作者在引言中声明全部证明成分均在文中给出。本结果族仅此一篇手稿，其技术骨架与两支姊妹文献互相支撑：三行方差不等式复证并推广了二部情形 Fu–Qin–Wang 的定理 5.1，精确采样套用 Göbel–Liu–Manurangsi–Pappik 的稀有残余混合框架。按 OpenAI 官方声明，未经形式化的结果可能存在问题，采用前请以待核验态度对待。
问 1：证明中最脆弱的一步在哪里？
答：不相交对项 @@M@@D@@ 的半正定性。无向图上不相邻顶点对的两条重采样会相互依赖，单个交叉项可为负；论文证明固定公共数据后依赖的秩至多一，负贡献由”两个邻居获得同一端点”的中心化指示投影控制，再借切片比较引理让负项成对相消。这一步是无向情形区别于 Caputo 交换子方法的独有难点，也是最可能藏缝隙的地方。
问 2：为什么不直接分析交换链，而绕道”对重采样”算子 @@M@@H@@？
答：对重采样把条件空间化成固定尺寸的均匀子集切片，使 Caputo 平方生成元方法可用：先证 @@M@@H^2\succeq H@@ 与核为常数，得 Poincaré 不等式，再经热浴比较 @@M@@H\preceq2n^2L@@ 折算回交换链谱隙。交换链本身没有这种块结构。
问 3：去掉”单个度向量可图化”之外的假设，前人卡在哪里？
答：此前的快速混合都在族级条件下证：正则性、度数的定量限制或 P-稳定（扰动后实现数之比多项式有界）。这些条件用于控制状态空间随扰动的膨胀；本文改证逐向量的方差不等式 @@M@@\operatorname{Var}_{\pi_d}(f)\le\langle f,Hf\rangle@@，完全绕开扰动比较。
问 4：@@M@@2n^8@@ 这个界是不是太松？最优混合时间是多少？
答：论文未讨论下界，@@M@@n^8@@ 谱隙上界 @@M@@[24n^2\binom n4]^{-1}@@ 与 @@M@@|\Omega_d|\le2^{\binom n2}@@ 组合的直接产物，未做优化。真实混合时间可能远小，文中没有展开。
问 5：AI 生成证明最可能出错的模式？
答：算子范数与常数簿记：三行方差不等式的常数 2（标签对换谱分解加相邻总量耦合两层论证）、秩一依赖的判定、@@M@@2n^8@@ 收尾的组合，任何一处系数滑动都可能悄悄破坏半正定性。本文未经形式化；幸运的是三行不等式复证了 Fu–Qin–Wang 定理 5.1，提供了一个外部交叉校验点。
问 6：谁会用到它？
答：网络科学的度保持零模型（configuration model 的精确版）立刻获得理论保证；推论 1.2 的精确均匀采样把”近似均匀”升级为”恰好均匀”；KTV 纲领剩下的有向情形仍是开放问题。
总评
这是悬置二十余年的 KTV 猜想在简单无向情形的完整解决，方法论上把谱分析换成逐向量方差不等式颇有巧思；最大风险是未经形式化且证明链条长而精密，半正定性论证需独立复核后才能放心引用。