结果族 188：The sharp terminal leave in random triangle removal · 学科：Combinatorics · 验证状态：暂无形式化证明，请以社区核验为准
想象一场”拆手链”游戏：n 个人两两拉手结成一张大网，每一轮随机挑出三个还彼此拉着手的幸运儿，让他们三人同时松开彼此的手；如此重复，直到再也凑不出三人互拉。散场时网上总会剩下一些零散的手——这篇论文精确算出了这些”剩手”的数量：约 @@M@@n^{3/2}/(2\sqrt2)@@ 条，连常数都分毫不差。从 1990 年 Bollobás–Erdős 猜测残尾规模为 @@M@@n^{3/2}@@ 起，指数早已确定，悬而未决的正是这个精确常数。
关键词卡片
@@M@@L^2@@ 收敛（@@M@@L^2@@ convergence）：结果与常数之差的平方平均趋于零，比”大概率接近”更强的说法。@@M@@1/(2\sqrt2)@@。看个具体例子
代入具体数字：@@M@@n=10^6@@ 时 @@M@@n^{3/2}=10^9@@，残尾约 @@M@@10^9/(2\sqrt2)\approx 3.5@@ 亿条——不管随机运气好坏，这个数几乎总是这么多。
为什么值得关心
一个被研究了三十多年的随机过程，其”最终垃圾量”被算到了精确常数，说明看似混乱的随机过程也可以有铁律般的精确定律。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读里把过程比作”拆手链”：n 个人两两相连，每轮随机挑出三名仍两两拉手的人，撤掉他们之间的三条连接，直到再也凑不出这样的三人组。去掉比喻但仍不用符号：研究对象是一张由连接构成的网，操作是每一步等可能地挑一个三边俱全的三角形、删去其全部三条边；终局残留的零散连接，正是本文要精确称量的东西。
第二级台阶
用本科图论的语言精确化：初始对象是 n 个顶点的完全图 K_n；上述随机程序称为一致三角形移除过程；被删掉的三角形拼成一个部分 Steiner 三元系；终止后残存的边集称为残尾，其边数记作 F_n。收敛采用均方（L²）意义——随机变量与常数之差的平方的期望趋于零，这比依概率收敛更强，还顺带控制了方差。
第三级台阶
定理在”从 K_n 出发的一致三角形移除”这一语境下陈述。”从完全图起步”的假设不可省略：它保证前期演化可交给 Joos–Kühn 已发表的前缀估计，在边密度降到 n^{-1/2+ε} 处刹车后，其余续跑估计全部本文自证；定理也不承诺任意起始图、一般超图移除的常数或波动规律。结论为：F_n/n^{3/2} 均方收敛于 1/(2√2)。这把残尾已知的 n^{3/2} 阶精确到常数，证明 Joos–Kühn 猜想的三角形情形，且比猜想要求的依概率收敛更强。
第一级台阶
导读里把过程比作”拆手链”：n 个人两两相连，每轮随机挑出三名仍两两拉手的人，撤掉他们之间的三条连接，直到再也凑不出这样的三人组。去掉比喻但仍不用符号：研究对象是一张由连接构成的网，操作是每一步等可能地挑一个三边俱全的三角形、删去其全部三条边；终局残留的零散连接，正是本文要精确称量的东西。
第二级台阶
用本科图论的语言精确化：初始对象是 n 个顶点的完全图 K_n；上述随机程序称为一致三角形移除过程；被删掉的三角形拼成一个部分 Steiner 三元系；终止后残存的边集称为残尾，其边数记作 F_n。收敛采用均方（L²）意义——随机变量与常数之差的平方的期望趋于零，这比依概率收敛更强，还顺带控制了方差。
第三级台阶
定理在”从 K_n 出发的一致三角形移除”这一语境下陈述。”从完全图起步”的假设不可省略：它保证前期演化可交给 Joos–Kühn 已发表的前缀估计，在边密度降到 n^{-1/2+ε} 处刹车后，其余续跑估计全部本文自证；定理也不承诺任意起始图、一般超图移除的常数或波动规律。结论为：F_n/n^{3/2} 均方收敛于 1/(2√2)。这把残尾已知的 n^{3/2} 阶精确到常数，证明 Joos–Kühn 猜想的三角形情形，且比猜想要求的依概率收敛更强。
证明了从完全图 @@M@@K_n@@ 出发随机逐个删三角形的终止残留边数 @@M@@F_n@@ 满足 @@M@@F_n/n^{3/2}@@ 依 @@M@@L^2@@ 收敛于 @@M@@1/(2\sqrt2)@@，首次敲定该过程的精确尾常数，解决 Joos–Kühn 猜想的三角形情形。
从 @@M@@n@@ 个顶点的完全图（complete graph）@@M@@K_n@@ 出发，每一步在三条边都还在的三角形中均匀选一个并删去其三条边，直到图中不再有三角形。被接受的三角形构成一个部分 Steiner 三元系（partial Steiner triple system），终止时残留的边称为残尾（leave），其边数记为 @@M@@F_n@@。Bollobás 与 Erdős 早在 1990 年就猜测 @@M@@\E F_n@@ 的阶为 @@M@@n^{3/2}@@。此后 Spencer 的分支过程分析与 Rödl–Thoma 的 nibble 方法先证残尾为 @@M@@o(n^2)@@，Grable 与 Bohman–Frieze–Lubetzky 又把上界逐步压到 @@M@@n^{7/4}@@ 量级乃至 @@M@@F_n=n^{3/2+o(1)}@@。指数虽已确定，精确常数却始终悬而未决：Joos 与 Kühn 在 2025 年关于严格平衡超图（strictly balanced hypergraph）移除过程的工作中猜想残尾有渐近常数，三角形情形为 @@M@@1/(2\sqrt2)@@。本文证明的正是这一情形。
主定理：对从 @@M@@K_n@@ 出发的一致三角形移除过程，
@@M@@D\E\left[\left(\frac{F_n}{n^{3/2}}-\frac{1}{2\sqrt{2}}\right)^{2}\right]\longrightarrow 0,@@
即 @@M@@F_n/n^{3/2}@@ 均方收敛（@@M@@L^2@@ convergence）于 @@M@@1/(2\sqrt2)@@。由此立即得到依概率收敛 @@M@@\frac{F_n}{n^{3/2}}\xrightarrow{\Prb}\frac{1}{2\sqrt{2}}@@，以及归一化期望极限 @@M@@\E F_n/n^{3/2}\to 1/(2\sqrt2)@@。这恰是 Joos–Kühn 猜想（其文献中的猜想 16.2）的三角形特款，且结论比猜想要求的依概率收敛更强。作者同时明确限定范围：定理只针对 @@M@@K_n@@ 起始的移除，不涉及任意起始图、一般超图移除的精确常数，也不给出波动规律（fluctuation law）。
先在确定性时刻”刹车”：当边密度降到 @@M@@p=n^{-1/2+\epsilon}@@（@@M@@\epsilon=1/2000@@）时停止。由 Joos–Kühn 的停止时间估计——这是全文唯一的外部证明输入——以超过 @@M@@1-\exp\bigl(-(\log n)^{4/3}\bigr)@@ 的概率，此刻的图有 @@M@@m=n^2p/2@@ 条边，每条边落在 @@M@@D=np^2@@ 个三角形中，且每个顶点链接图（link graph）的圈计数与有根模板（rooted template）计数都近乎理想，这是后续一切估计的公共起点。
再把续跑过程改写为优先级扫描：给三角形赋予独立均匀优先级，从小到大扫描，三边俱全即接受。一条边的存活等价于一个递归测试返回真，其子测试询问候选三角形的另外两条边是否先于该候选存活；两条边合用一份联合有序候选表。若给递归树中每次出现都配上全新的独立优先级，就得到”独立展开”（independent unfolding）模型，其中存活概率满足精确的乘积恒等式，可与 Spencer 分支过程的标量解 @@M@@q(t)=(1+2Dt)^{-1/2}@@ 比较。
然后攻克两个难点。其一为稳定性：不同边的偏差沿三角形的边邻接矩阵 @@M@@A/D@@ 传播，朴素的极大范数界要损失 @@M@@D@@ 倍。作者用链接圈计数做谱分离，使链接矩阵除主特征值外均为 @@M@@O(n^{-\gamma})@@、在欧氏范数下接近平均化投影，再经有限扰动展开把半群的极大范数界压到多对数级 @@M@@C_1(1+\log n)^J@@，自举闭合得 @@M@@q_e(t)=(1+o(1))q(t)@@ 对所有边一致成立。其二为碰撞：真实过程中同一三角形类型会在不同查询里重现，独立展开则不会；耦合分析表明每次重现都迫使两条祖先查询路径之并上多出一条图边（见证，witness）。用有根模板界数出这类嵌入的数目，关键增益为 @@M@@D^{-B}@@（@@M@@B=50@@）；而访问指定路径既要求优先级沿路递减（@@M@@1/j!@@ 因子），又要求偏离路径的候选全部失败（每步 @@M@@q^2@@ 因子），二者相乘并对路径长度求和得碰撞概率 @@M@@O(D^{-35})=o(D^{-1})@@——这一精度必须小于双根存活概率自身的阶 @@M@@(2D)^{-1}@@，否则二阶矩无法成立。
最后读出矩：一或两个均匀随机根边的查询成功率分别给出 @@M@@\E[F_n/m]@@ 与 @@M@@\E[(F_n/m)^2]@@，而 @@M@@mq(1)=\frac{n^2p}{2\sqrt{1+2np^2}}\sim\frac{n^{3/2}}{2\sqrt{2}}@@，坏前缀的贡献又被其超多项式小的失败概率吸收，于是无条件地得到 @@M@@L^2@@ 收敛与常数 @@M@@1/(2\sqrt2)@@。
本手稿（OpenAI，2026 年 9 月 25 日）主结果尚无 Lean 形式化证明；按 OpenAI 官方声明，未经形式化的结果可能存在问题，请以社区核验为准。除引用 Joos–Kühn 已公开的前缀估计外，其余关键续跑估计——半群的极大范数稳定性与 @@M@@o(D^{-1})@@ 的成对查询碰撞界——均为本文自证，逻辑链前后闭环。本批任务中该结果族仅含此一篇手稿，暂无姊妹篇交叉支撑；其结论与此前 @@M@@F_n=n^{3/2+o(1)}@@ 的指数级结果相容，并将常数精确到 @@M@@1/(2\sqrt2)@@。
问 1：证明里最关键也最脆弱的一步在哪里？
答：成对查询的碰撞控制。第二矩需要两条根边的联合存活概率，它本身只有约 (2D)^{-1} 量级，故独立展开与真实过程的偏差必须压到 o(D^{-1})。见证计数要求路径优先级递减（1/j! 因子）与离路候选全败（每步 q² 因子）相乘，再配 rooted-template 界的 D^{-B}（B=50）增益得到 O(D^{-35})；任何一处常数损耗或依赖漏算都可能让精度跌破 1/D，二阶矩随即失效。
问 2：为什么要在边密度 n^{-1/2+ε} 处”刹车”，ε=1/2000 为何这么小？
答：刹车点之前依赖 Joos–Kühn 的前缀估计保证伪随机性（每边恰有 D=np² 个三角形、链接图圈数近乎理想），刹车点之后全靠本文自证的稳定性与碰撞界。ε 太大则 D 太小，谱分离与模板界不够用；ε 太小则前缀太长、失败概率难以吸收。论文未讨论 ε 的最优选取，只验证 1/2000 能让各参数同时成立。
问 3：与 Bohman–Frieze–Lubetzky 的 F_n=n^{3/2+o(1)} 相比，真正的新意是什么？
答：他们用自校正动态集中不等式定指数；本文把续跑改写为优先级扫描加递归存活测试，在随时间增长的区间上逼近联合存活概率——引言明言固定时刻的局部近似达不到二阶矩所需精度。新的关键估计有二：展开的极大范数稳定性、自适应成对查询的 o(D^{-1}) 误差；常数与矩结论都靠它们。
问 4：为什么假设”从 K_n 起步”不能换成任意起始图？
答：前缀控制是唯一外部输入，只对完全图出发的过程成立；一般起始图缺少每边 D=np² 个三角形与链接圈计数的伪随机保证，续跑分析无从启动。论文明确声明不主张任意起始图或一般超图移除的精确常数。
问 5：AI 生成证明最可能在哪里出错？
答：典型风险是递归查询间的隐蔽相关——独立展开给每次出现配新优先级，而真实过程同一三角形类型会重现；耦合论证要求每次重现都在两条祖先查询路径之并上产生图上见证边，这一对应若有例外未被计入，碰撞界就系统性低估。此外多对数级半群界与 D^{-35} 的组合涉及大量常数簿记，最易出算术错。论文未提供对这两点的机器核验。
问 6：这个结果谁会用到？
答：随机贪婪超图匹配与严格平衡超图移除的研究者——它验证了 Joos–Kühn 猜想 16.2 的第一个精确常数情形，为一般严格平衡图的常数问题提供方法模板；部分 Steiner 三元系的随机构造亦直接受益。波动规律（如 CLT）论文未展开，仍是空白。
总评
把三十余年悬而未决的残尾常数钉死在 1/(2√2)，且给出强于猜想的 L² 收敛，分量十足；最大风险在 o(D^{-1}) 碰撞界的耦合完备性与常数簿记，未经形式化前宜按”高置信待核验”对待。
问 1：证明里最关键也最脆弱的一步在哪里？
答：成对查询的碰撞控制。第二矩需要两条根边的联合存活概率，它本身只有约 (2D)^{-1} 量级，故独立展开与真实过程的偏差必须压到 o(D^{-1})。见证计数要求路径优先级递减（1/j! 因子）与离路候选全败（每步 q² 因子）相乘，再配 rooted-template 界的 D^{-B}（B=50）增益得到 O(D^{-35})；任何一处常数损耗或依赖漏算都可能让精度跌破 1/D，二阶矩随即失效。
问 2：为什么要在边密度 n^{-1/2+ε} 处”刹车”，ε=1/2000 为何这么小？
答：刹车点之前依赖 Joos–Kühn 的前缀估计保证伪随机性（每边恰有 D=np² 个三角形、链接图圈数近乎理想），刹车点之后全靠本文自证的稳定性与碰撞界。ε 太大则 D 太小，谱分离与模板界不够用；ε 太小则前缀太长、失败概率难以吸收。论文未讨论 ε 的最优选取，只验证 1/2000 能让各参数同时成立。
问 3：与 Bohman–Frieze–Lubetzky 的 F_n=n^{3/2+o(1)} 相比，真正的新意是什么？
答：他们用自校正动态集中不等式定指数；本文把续跑改写为优先级扫描加递归存活测试，在随时间增长的区间上逼近联合存活概率——引言明言固定时刻的局部近似达不到二阶矩所需精度。新的关键估计有二：展开的极大范数稳定性、自适应成对查询的 o(D^{-1}) 误差；常数与矩结论都靠它们。
问 4：为什么假设”从 K_n 起步”不能换成任意起始图？
答：前缀控制是唯一外部输入，只对完全图出发的过程成立；一般起始图缺少每边 D=np² 个三角形与链接圈计数的伪随机保证，续跑分析无从启动。论文明确声明不主张任意起始图或一般超图移除的精确常数。
问 5：AI 生成证明最可能在哪里出错？
答：典型风险是递归查询间的隐蔽相关——独立展开给每次出现配新优先级，而真实过程同一三角形类型会重现；耦合论证要求每次重现都在两条祖先查询路径之并上产生图上见证边，这一对应若有例外未被计入，碰撞界就系统性低估。此外多对数级半群界与 D^{-35} 的组合涉及大量常数簿记，最易出算术错。论文未提供对这两点的机器核验。
问 6：这个结果谁会用到？
答：随机贪婪超图匹配与严格平衡超图移除的研究者——它验证了 Joos–Kühn 猜想 16.2 的第一个精确常数情形，为一般严格平衡图的常数问题提供方法模板；部分 Steiner 三元系的随机构造亦直接受益。波动规律（如 CLT）论文未展开，仍是空白。
总评
把三十余年悬而未决的残尾常数钉死在 1/(2√2)，且给出强于猜想的 L² 收敛，分量十足；最大风险在 o(D^{-1}) 碰撞界的耦合完备性与常数簿记，未经形式化前宜按”高置信待核验”对待。