结果族 171：The hypercube Ramsey conjecture · 学科：Combinatorics · 验证状态：暂无形式化证明，请以社区核验为准
@@M@@n@@ 维立方体像一排 @@M@@n@@ 个开关的全部 @@M@@2^n@@ 种组合状态。把一个足够大的完全图随意染成红蓝两色，问要多大才能保证”整只立方体”颜色纯正地现身？Burr 与 Erdős 1975 年猜测：顶点数的常数倍足矣。本文证明他们猜对了。
关键词卡片
@@M@@Q_n@@：@@M@@n@@ 个 0/1 开关的全部 @@M@@2^n@@ 种组合，相差一个开关就连边@@M@@R(H)@@：保证任意红蓝染色含单色 @@M@@H@@ 的最小完全图规模@@M@@Q_n@@ 的退化度等于 @@M@@n@@，随维度增长，旧定理用不上看个具体例子
以 @@M@@n=10@@ 为例：@@M@@Q_{10}@@ 有 @@M@@1024@@ 个顶点，经典两色下界给出 @@M@@R(Q_{10})\ge 3\cdot 2^9-1=1535@@，定理给出 @@M@@R(Q_{10})\le 1024C@@——也就是说，把超过 @@M@@C\times1024@@ 个顶点的完全图随手染色，单色的十维立方体必然浮现。两边只差常数倍，故 @@M@@R(Q_n)=\Theta(2^n)@@：此前最好的上界是 @@M@@2^{2n-cn}@@，离线性还差整整一个指数。
为什么值得关心
1975 年提出的超立方体拉姆齐猜想彻底解决；立方体恰好卡在”线性拉姆齐数”必要条件的密度门槛上（边点比是允许值的上限），是最紧的一类测试图。
暂无形式化证明（AI 结果待核验）
第一级台阶
入门导读把 @@M@@n@@ 维立方体想成”@@M@@n@@ 个开关的全部 @@M@@2^n@@ 种组合状态”，把问题想成”把足够大的完全图随手染成红蓝，整只立方体终会纯色现身”。剥掉比喻：对象是一族图——超立方体，两个状态恰差一个开关就连边；操作是对更大的完全图做任意红蓝边染色；要证的是把单色立方体逼出来所需的规模只是立方体顶点数的常数倍。
第二级台阶
用本科语言精确化：@@M@@R(H)@@ 是使 @@M@@K_M@@ 的每条红蓝边染色都含单色 @@M@@H@@ 的最小 @@M@@M@@；称图族为 @@M@@L@@-set，若一个常数乘顶点数即可支配全族的拉姆齐数。立方体的临界性在于密度：线性拉姆齐数的必要条件是 @@M@@e/v=O(\log v)@@，而 @@M@@Q_n@@ 的边点比 @@M@@n/2@@ 恰等于 @@M@@\tfrac12\log_2|V|@@，顶在所允许的最大阶；其最大度与退化度都是 @@M@@n@@，随维度增长，固定度或固定退化度的线性定理常数随之爆炸。
第三级台阶
主定理：存在绝对常数 @@M@@C@@，对一切 @@M@@n\ge0@@ 有 @@M@@R(Q_n)\le C2^n@@；配上两块染色的经典下界 @@M@@3\cdot2^{n-1}-1@@，阶被确定为 @@M@@\Theta(2^n)@@。反证框架假设存在无单色 @@M@@Q_n@@ 的反例序列，宿主规模满足 @@M@@N/2^n\to\infty@@ 但无指定速度——”无速度”挡住了对发散率的任何取巧。定理不给 @@M@@C@@ 的数值，也不判定 @@M@@R(Q_n)/2^n@@ 是否收敛；枢纽是”偏差对纯净”引理：颜色密度一旦偏离一半，就逼出近乎单色的大块。
证明了 @@M@@n@@ 维超立方体图 @@M@@Q_n@@ 的双色拉姆齐数满足 @@M@@R(Q_n)\le C2^n@@（@@M@@C@@ 为绝对常数），结合经典下界 @@M@@R(Q_n)\ge 3\cdot2^{n-1}-1@@ 得 @@M@@R(Q_n)=\Theta(2^n)@@，正面解决了 Burr 与 Erdős 1975 年提出的超立方体拉姆齐猜想。
拉姆齐数（Ramsey number）@@M@@R(H)@@ 是使完全图 @@M@@K_M@@ 的每条红蓝边染色都含单色 @@M@@H@@ 的最小 @@M@@M@@。1975 年 Burr 与 Erdős 称一个图族为 @@M@@L@@-set，若一个常数乘顶点数即可支配族中所有成员的拉姆齐数；他们猜想一致有界退化度（degeneracy）的图族都是 @@M@@L@@-set，并在同文第 7 节单独提问：@@M@@n@@ 维立方体 @@M@@Q_n@@（顶点为 @@M@@\{0,1\}^n@@，两点恰差一个坐标时相邻）是否构成 @@M@@L@@-set。立方体恰好卡在此问题的密度门槛上：线性拉姆齐数要求 @@M@@e(H)/|V(H)|=O(\log|V(H)|)@@，而 @@M@@Q_n@@ 的边点比恰为 @@M@@\tfrac12\log_2|V|@@，是必要条件所允许的最大阶。固定最大度（Chvátal–Rödl–Szemerédi–Trotter 1983）与固定退化度（Lee 2017）的线性定理常数都依赖度数或退化度，而 @@M@@Q_n@@ 的这两个参数都等于 @@M@@n@@，故用不上；此前最好上界是 Tikhomirov 2024 年的 @@M@@2^{2n-cn+1}+2@@，距线性还差一个指数。
主定理：存在绝对常数 @@M@@C>0@@，对一切整数 @@M@@n\ge0@@ 有 @@M@@R(Q_n)\le C2^n@@。配上两块染色的下界，@@M@@R(Q_n)@@ 的阶被确定为 @@M@@\Theta(2^n)@@：在常数倍于立方体顶点数的完全图上做任何红蓝染色，必出现单色 @@M@@n@@ 维立方体。论文不给 @@M@@C@@ 的数值，也不判定 @@M@@R(Q_n)/2^n@@ 是否收敛。推论：若 @@M@@H@@ 是某 @@M@@Q_d@@ 的子图且 @@M@@2^d\le A|V(H)|@@，则 @@M@@R(H)\le CA|V(H)|@@；特别地，@@M@@Q_d@@ 的任何支撑子图 @@M@@F@@ 的笛卡尔幂（Cartesian power）@@M@@F^{\square k}@@ 满足 @@M@@R(F^{\square k})\le C|V(F)|^k@@，常数对所有 @@M@@F,d,k@@ 一致。
全文用反证法沿序列推进。先归约：若 @@M@@R(Q_n)/2^n@@ 无界，可取到两侧各 @@M@@N@@ 个宿主标签、跨边红蓝染色、无单色 @@M@@Q_n@@ 的反例序列，满足 @@M@@n\to\infty@@、@@M@@C_n=N/2^n\to\infty@@（不设速度）、@@M@@N\le n2^n@@。嵌入框架是：立方体顶点称”角色”、宿主顶点称”标签”，偶角色放 @@M@@X@@ 侧、奇角色放 @@M@@Y@@ 侧；奇角色注入后，偶角色 @@M@@v@@ 只能落在其已放奇邻居在该色下的公共邻域 @@M@@L_v@@ 里。只要给每个偶角色造一个支集含于 @@M@@L_v@@ 的次概率测度 @@M@@p_v@@，且每个标签上的列和 @@M@@\le1@@，Hall 定理便给出两两不同的偶标签，嵌入即告完成。
证明分四阶段。第一阶段备好概率工具：稳定化引理沿子列删去 @@M@@o(N)@@ 标签，使每条性质”要么消失、要么在任意小删除后仍可用”；用角谷不动点定理平衡各补丁（patch）律的期望标签负载；另有偏侧局部引理式的条件回避比较、门控后验比较（处理”数据被选择”引入的偏倚），以及两个保持精确边际且联合概率近乘积的注入采样器（校准近乘积注入与时钟采样）。
第二阶段是枢纽性的”偏差对纯净”（bias versus purity）引理：若某宽度（width，度量概率律集中程度的量 @@M@@\log(N\max_x\mu(x))@@）预算下的律对看到密度偏离 @@M@@1/2@@ 达 @@M@@n^{-h}@@，则除非已能嵌出立方体，加倍宽度处必出现近乎单色的纯净块。于是在反例中两色在一切幂宽度上都无偏差。其数值机制在于：每条公共邻域限制约保留一半质量，@@M@@n@@ 条连乘损失 @@M@@2^{-n}@@，而密度盈余按 @@M@@(1/2+\delta)^n@@ 指数累积，恰好补偿支集的缩小——@@M@@2^n@@ 因子正是在这里被”吃掉”的。
第三、四阶段做平铺与收尾：沿用立方体对固定团问题中的几何，按固定初始坐标的子立方体把 @@M@@Q_n@@ 切分、分配给一块块同色同取向的补丁；增益足够大时先注入奇角色，用分散矩估计控制偶侧列和后走 Hall；增益不足时用一个固定线性映射把奇角色分成校验子类（syndrome class），只给 @@M@@O(\log n)@@ 个类临时标签，再逐类从保留集换牌，使每个偶角色始终留有两个候选，最后对随机二元候选对做联合估计排除 Hall 缺陷。此外，一个受 Lipschitz 渗流启发的”几何高度”装置在汉明球中逐层选中心，保证相邻角色的选择相容。四阶段在反例上造出单色 @@M@@Q_n@@，得到矛盾。
本文属 OpenAI 波次成果，主结果暂无 Lean 形式化证明，请以社区核验为准；OpenAI 官方声明”未经形式化的结果可能有问题”。论文与 Tikhomirov 2024 的途径互补：那边证明一色密度定理，这边从两色反例同时导出偏差。作为结果族 171 的核心篇，它把上界从 @@M@@2^{2n-cn}@@ 一步压到线性阶，文中关于立方体子图与笛卡尔幂的推论均由主定理直接派生。
问 1：整个证明的枢纽在哪里，@@M@@2^n@@ 因子是在哪一步被”吃掉”的？
（答：”偏差对纯净”引理。若某宽度预算下的律对看到密度偏离 @@M@@1/2@@ 达 @@M@@n^{-h}@@，则除非已能嵌出立方体，加倍宽度处必现近乎单色的纯净块。数值机制是：每条公共邻域限制约保留一半质量，@@M@@n@@ 条连乘损失 @@M@@2^{-n}@@，而密度盈余按 @@M@@(1/2+\delta)^n@@ 指数累积恰好补偿支集缩小——反例中两色于是都无偏差，平铺与收尾才能展开。）
问 2：1983 年就有”固定最大度 @@M@@\Rightarrow@@ 线性拉姆齐数”，立方体为什么拖了五十年？
（答：Chvátal–Rödl–Szemerédi–Trotter 与 Lee 的定理常数依赖度数或退化度，而 @@M@@Q_n@@ 的这两个参数都等于 @@M@@n@@。更深的障碍是密度：线性拉姆齐数必要条件允许 @@M@@e/v=O(\log v)@@，立方体的 @@M@@n/2@@ 恰顶在最大允许阶——它是对该条件最紧的测试图，任何损失指数的嵌入法都会失效。）
问 3：与 Tikhomirov 2024 的 @@M@@2^{2n-cn+1}@@ 相比，方法差异的本质是什么？
（答：Tikhomirov 证的是单色密度定理——密度 @@M@@\ge1/2@@、两部各 @@M@@\ge2^{(2-c)n}@@ 的二部图必含 @@M@@Q_n@@；本文从两色都无立方体的反例同时导出偏差。且本文宿主只是 @@M@@2^n@@ 的缓慢发散倍，须全程保住常数乘损失，这比”指数改进”严格更强。）
问 4：哪个设定撤掉就崩？
（答：”@@M@@N/2^n\to\infty@@ 无指定速度”。反例序列不设发散率，意味着所有引理须在任意慢的发散下成立，稳定化引理只能删去 @@M@@o(N)@@ 个标签；若允许假设速度，许多估计会平凡化，常数 @@M@@C@@ 就会退化成 @@M@@n@@ 的函数。）
问 5：最可能出错的模式？
（答：概率机器的精细咬合。稳定化、角谷不动点平衡补丁期望负载、门控后验比较处理”数据被选择”的偏倚、保持精确边际且联合概率近乘积的注入采样器——每件工具单看标准，组合起来对边际与联合分布的同时控制最易出隐患；全文未形式化。）
问 6：论文自己承认的局限是什么？
（答：不给 @@M@@C@@ 的数值，也不判定 @@M@@R(Q_n)/2^n@@ 是否收敛及其极限。下界 @@M@@3\cdot2^{n-1}-1@@ 与上界 @@M@@C\cdot2^n@@ 之间的常数隙是天然的下一步。）
问 7：谁受益？
（答：拉姆齐理论社区之外，推论即时覆盖立方体的稠密子图（@@M@@2^d\le A|V(H)|\Rightarrow R(H)\le CA|V(H)|@@）与支撑子图的笛卡尔幂 @@M@@F^{\square k}@@（@@M@@R\le C|V(F)|^k@@，常数对一切 @@M@@F,d,k@@ 一致）——后者连 Mota–Sárközy–Schacht–Taraz 的固定度框架都给不出。）
总评
1975 年 Burr–Erdős 问题的彻底解决，上界从差一个指数一步压到线性阶，且是在密度门槛最紧的测试图上做到；最大风险是未形式化的庞大概率机器，任何一处边际控制失守都可能使常数变成 @@M@@n@@ 的函数。