结果族 178：Deterministic nonbipartite Ramanujan graphs in every fixed degree · 学科：Combinatorics · 验证状态：暂无形式化证明，请以社区核验为准
每张网络都有自己的”振动频率”（特征值）：非平凡频率越小，网络越均匀、信息扩散越快。Ramanujan 图是频率恰好压在理论天花板上的完美网络，此前人们只能在特定度数或”带误差”的条件下确定性地造它。这篇论文造出了全自动机床：你指定顶点数和度数，它直接打印一张精确达标的网。
关键词卡片
@@M@@\pm2\sqrt{d-1}@@ 内的 d-正则图。看个具体例子
定理：对每个 d≥3 与充分大的偶数 n，算法在多项式时间内输出简单非二部 d-正则图，其一切非平凡特征值满足 @@M@@-2\sqrt{d-1}<\lambda<2\sqrt{d-1}@@。代入 d=3：全部非平凡频率严格落在 ±2.83 之间（下图蓝点），而平凡频率 3 独居界外。随机正则图本身早已以高概率近似达标——难的从来不是存在，而是把”扔骰子碰运气”换成一步步确定的工序，还要精确压线、不带一丝误差。
为什么值得关心
这是首个同时做到精确谱界、指定偶数阶、非二部与确定性多项式时间的构造，扩张图的”按需生产”成为可能。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读把网络的特征值比作”振动频率”，Ramanujan 图是频率恰好压在理论天花板上的完美网络，而论文造出了”指定参数、直接打印”的机床。翻译成半数学语言：对象是每个顶点恰好连出 d 条边的简单无向图；操作是给每个顶点预装 d 个可区分的半边、再逐步配对成边的确定性工序；指标是全部非平凡频率都要严格落在由无穷正则树决定的谱半径之内。
第二级台阶
用本科线性代数术语精确化。图 G 的邻接矩阵 A_G 的特征值刻画振动频率；d-正则使常向量对应平凡特征值 d，其余特征值落在其正交补上。若这些非平凡特征值都严格介于 −2√(d−1) 与 2√(d−1) 之间——无穷 d-正则树的谱半径——则称 G 是 Ramanujan 图；Alon–Boppana 界说明顶点数增大时该区间无法再收紧。二部图会多出 −d 频率，非二部要求双侧都压线。
第三级台阶
定理陈述：对每个固定度 d ≥ 3 与每个充分大的偶数 n，确定性算法以 O_d(n^{k_d}) 位操作输出简单非二部 d-正则 Ramanujan 图的完整邻接表，k_d 可依赖 d。”偶数阶”挡住了奇度正则图在奇数阶上无法存在的组合障碍；由 d > 2√(d−1)，界自动排除 ±d，图连通且非二部。此前算术构造只在特定度数精确达标，二部情形由 MSS 的二提升解决，非二部确定性构造长期带正误差 ε——本文首次去掉 ε，实现精确双侧谱界。
对每个固定度 @@M@@d\ge 3@@，本文在每个充分大的偶数阶 @@M@@n@@ 上确定性构造简单、非二部（nonbipartite）的 @@M@@d@@-正则 Ramanujan 图：全部非平凡特征值严格落在 @@M@@(-2\sqrt{d-1},\,2\sqrt{d-1})@@ 内，并以多项式位操作输出完整邻接表——首次把精确谱界、指定阶数与确定性同时实现。
@@M@@d@@-正则图称为 Ramanujan 图，若其邻接矩阵（adjacency matrix）限制在常向量正交补 @@M@@\mathbf1^\perp@@ 上的范数不超过 @@M@@2\sqrt{d-1}@@；这正是无穷 @@M@@d@@-正则树的谱半径，而 Alon–Boppana 界说明该阈值渐近最优，非平凡谱小意味着边分布接近均匀预测、扩张性好。1988 年 Lubotzky–Phillips–Sarnak 与 Margulis 的算术构造只在特定度数达到精确阈值，Morgenstern 推广到 @@M@@q+1@@；Bilu–Linial 的二提升（two-lift）路线经 Marcus–Spielman–Srivastava 的交错多项式（interlacing polynomials）方法解决了任意度数的二部情形，但对非二部简单图，确定性构造的最好结果长期停留在带正误差的 @@M@@2\sqrt{d-1}+\varepsilon@@（Mohanty–O’Donnell–Paredes 2020；Alon 2021）。去掉这个 @@M@@\varepsilon@@，必须在特征值到两条树边缘距离的精细尺度上控制谱，正是卡点所在。另一侧，Friedman 与 Bordenave 证明随机正则图近似 Ramanujan，Huang–McKenzie–Yau 的联合边缘普适性进一步给出精确 Ramanujan 事件概率趋于约 0.69——存在性早已无虞，缺的是确定性的精确构造。
定理 1.1：对每个整数 @@M@@d\ge 3@@，存在常数 @@M@@n_0(d)@@、@@M@@k_d@@ 与一个确定性算法，输入任意偶数 @@M@@n\ge n_0(d)@@，它以 @@M@@O_d(n^{k_d})@@ 位操作输出一个简单 @@M@@d@@-正则图 @@M@@G@@ 的邻接表，且 @@M@@A_G|_{\mathbf1^\perp}@@ 的每个特征值 @@M@@\lambda@@ 都满足 @@M@@-2\sqrt{d-1}<\lambda<2\sqrt{d-1}@@。由 @@M@@d>2\sqrt{d-1}@@（当 @@M@@d\ge3@@），该界自动排除多余的 @@M@@\pm d@@ 特征值，故 @@M@@G@@ 连通且非二部。推论 1.2：对任意充分大的目标规模 @@M@@N@@，算法给出满足全部上述性质的图，阶数落在 @@M@@N@@ 与 @@M@@N+1@@ 之间。注意：指数 @@M@@k_d@@ 可以依赖 @@M@@d@@，论文不声称关于 @@M@@n,d@@ 联合的多项式时间，也不提供局部邻接查询算法；”显式”专指输出整个邻接表。相对既有工作，这一构造首次同时做到：简单图（非多重图）、非二部（双侧谱界）、精确阈值（无 @@M@@\varepsilon@@）、指定偶数阶与确定性多项式时间。
总体策略是把随机正则图谱分析中的局部树逼近改造成完全确定性的构造。先给每个顶点 @@M@@d@@ 个可区分的半边（stub），逐步配对成边。全程对两个符号 @@M@@\sigma=\pm1@@ 维护正定的 precision 矩阵（完工时即 @@M@@zI-\sigma A_G@@，@@M@@z>s@@，@@M@@s=2\sqrt{d-1}@@），其归一化逆与截断加权的非回溯路径（nonbacktracking path）之和逐项比较；对完工图，这条路径递推正对应正则图的 Ihara–Bass 束 @@M@@I-\sigma hA_G+(d-1)h^2I@@。每一步配对按”折算账本”（discounted accounts）规则选取加权统计量的最小化者——这是条件期望法与悲观估计子（pessimistic estimator）的确定性化，每个统计量带各自的折算因子，一次选择同时保住所有估计。
具体分四个阶段。先做早期配对，从空配对出发配掉绝大多数 stub：难点是在长序列选择中同时控制多项式多个条目，关键引理证明高阶矩的增长系数与矩阶无关，故取一个足够大的固定矩即可提取出最大值界。再在清理阶段把相互靠近或产生短返回的 stub 配掉，使剩余 @@M@@l_0\asymp n^{2/3}@@ 个 stub 位于不同顶点、两两分离且无短非回溯返回。随后补全阶段以 Woodbury 恒等式对冻结的光滑路径参考做精确低秩逆更新：先压低行能量平方、再用变小的能量改进入口逐项界，这使最后几个 stub 可以任意匹配，最终得到非平凡谱落在 @@M@@(-s-e/20,\,s+e/20)@@ 内的简单正则图，其中 @@M@@e=n^{-2/3+a}@@，@@M@@a=10^{-4}@@。
最后是精确修复定理——去掉残余误差的关键。它只需三个输入：谱约束（松弛量 @@M@@x_i^\sigma=s-\sigma\lambda_i>-e/20@@）、每点局部谱质量界 @@M@@\sum_{x_i^\sigma\le w}|v_i(p)|^2\le Cw^{3/2}@@，以及绝大多数边的 bulk 预解算子 @@M@@R_B^\sigma@@ 的 @@M@@2\times2@@ 端点块接近树块 @@M@@\frac{1}{d-2}\begin{pmatrix}\sqrt{d-1}&\sigma\\ \sigma&\sqrt{d-1}\end{pmatrix}@@。先用 Schur 补（即 Woodbury 恒等式加惯性论证）消去 bulk 模式，把正性化为近边缘模式上的二次型。此处有个关键观察：均匀随机换边的均值修正只会把每个松弛量乘以 @@M@@1-o(1)@@，救不了负松弛；于是对两条被选边的联合分布做倾斜（tilt），在最接近阈值的模式上注入远大于 @@M@@e@@ 的正均值偏移，压过 @@M@@-e/20@@ 的负松弛，其余近边缘模式仍保留固定比例的正余量。涨落与端点碰撞仅用二阶矩估计（成对独立即可）。确定性化时，先用 Bernstein 多项式作用于有理矩阵逼近倾斜律，再在素域 @@M@@\mathbb F_P@@ 上用仿射构造生成成对独立样本、枚举全部 @@M@@P^2@@ 个种子，对每个候选图以精确有理惯性检验 @@M@@B^T(4qI-A_{G'}^2)B\succ0@@（@@M@@q=d-1@@，@@M@@B@@ 为 @@M@@\mathbf1^\perp@@ 的有理基）；修复定理保证搜索中必有通过者。
主结果尚无 Lean 形式化证明，请以社区核验为准；OpenAI 官方亦声明”未经形式化的结果可能有问题”。本结果族目前仅此一篇手稿，无姊妹篇互相印证；其外部支点是 MSS/HPS 的二部情形构造与 Huang–McKenzie–Yau 的存在性定理，而沿确定性配对历史的谱估计与双侧倾斜修复是本文新证。算法端全部为精确有理计算（Bareiss 分数无关消元、精确惯性判定），最终的谱检验原则上可被机器无条件复核，这是可信度的实质加分项。
问 1：证明中最关键的一步是什么？
答：精确修复定理（repair 一节）。补全阶段只能把非平凡谱压进 (−s−e/20, s+e/20)，e = n^{-2/3+a}；修复定理以三个输入——各模式松弛量 x_i^σ = s − σλ_i > −e/20、每点局部谱质量 ≤ Cw^{3/2}、bulk 预解算子 2×2 端点块接近树块——经 Schur 补消去 bulk 模式，再对两条被选边的联合分布做倾斜（tilt），在最接近阈值的模式注入远大于 e 的正均值偏移。关键观察是均匀换边的均值修正只乘 1−o(1)、救不了负松弛，倾斜因此是必需的。
问 2：为什么此前去不掉那个 ε？本文凭什么去掉？
答：MSS 的交错多项式路线天然给出二部图，非二部需要双侧同时压线；Mohanty–O’Donnell–Paredes 与 Alon 的确定性构造停在 2√(d−1)+ε，因为谱只在”到树边缘距离”的粗尺度上受控。本文把随机正则图的局部树逼近改造成确定性配对历史：precision 矩阵的归一化逆与截断加权的非回溯路径逐项比较，完工时对应 Ihara–Bass 型刻画，才把控制推进到边缘的精细尺度。
问 3：哪些假设是让步、能否去掉？
答：定理只对偶数 n、指数 k_d 依赖 d，论文明言不声称 (n,d) 联合多项式时间、也不提供局部邻接查询算法——”显式”专指输出整张邻接表。奇度 d-正则简单图在奇数阶不存在，偶数限制至少对奇 d 是硬的；k_d 依赖 d 源于倾斜枚举与常数选择，论文未讨论能否改进。
问 4：与已有工作相比真正的新意是什么？
答：首次同时做到：简单图、非二部、精确阈值无 ε、指定偶数阶、确定性多项式时间。存在性一侧 Huang–McKenzie–Yau 已给出精确 Ramanujan 事件概率约 0.69，难的全在确定性；本文的确定性化用具折算账本的悲观估计子（条件期望法）、Bernstein 多项式逼近倾斜律、素域 F_P 上成对独立样本枚举 P^2 个种子。
问 5：AI 生成证明最可能出错的模式？
答：本文未形式化且无姊妹篇互证，是最需要警惕的一篇。风险集中在修复定理的二阶矩估计与倾斜律的有理逼近误差是否真的压过 −e/20 的负松弛，以及 Woodbury 低秩更新的行能量账目。实质加分项是：最终检验 B^T(4qI−A_{G’}^2)B ≻ 0 是精确有理惯性判定，输出可被机器无条件复核——出错的只会是”搜索必有通过者”这层证明，而非图本身。
问 6：非二部性从哪里来？
答：不是单独构造，而是谱界的推论：d ≥ 3 时 d > 2√(d−1)，严格双侧界自动排除 −d 与多余 +d，故图连通且非二部（推论 1.2 的规模版本同理由成立）。
问 7：谁会用到它？
答：理论计算机科学中需要任意给定规模的显式扩张图的场景：去随机化、差错码与网络拓扑设计都可”按需下单”；谱图理论社区则得到首个精确非二部模型，可用来检验谱方法的最优常数。
总评
这是 Ramanujan 图”按需生产”问题的收官级构造，技术纵深极大；最大风险是未经形式化、无姊妹篇互证，全部赌注压在修复定理与倾斜论证的正确性上——好在最终产物可精确复核。