双层床猜想的最小反例边界：小基础图的符号精确验证与加权变体的反例搜索

1 · 研究问题

双层床猜想（bunkbed conjecture，Kasteleyn 1985；2024 年被 Gladkov–Pak–Zimin 用 7222 顶点平面图证伪）的最小反例可以多小？基础图 ≤ 5 个顶点范围内能否符号精确地排除反例，加权（每边独立参数）变体在 ≤ 7 个顶点内是否已出现反例？

2 · 研究背景与空白

猜想断言：在图 G 的双层床图（两份 G 由横档边相连）中，同层两点的连通概率不小于跨层连通概率。Gladkov–Pak–Zimin（arXiv:2410.02545, PNAS 2025）基于 Hollom 的超图反例构造出 7222 顶点、14422 边的图反例，概率差仅 10^-6500 量级；已证成立的类包括完全图（van Hintum–Lammers）、森林（2025 初等证明，arXiv:2511.13589）、轮图等，且顶点粘合保持猜想（arXiv:2410.08957）。GPZ 明确表示曾试探小图未果，且认为加权版本更可能出小反例，但均未发布系统的穷举验证记录。

空白在"最小反例规模的下界"没有任何已发表的系统数据。适合仅限"接受高风险"的学生：无反例的负结果（含逐图安全间隙 margin 表）依然构成完整论文；找到远小于 7222 的反例则是顶级结果。

历届对照：2021 年优胜《Lower Bound of Bernoulli Percolation in the Critical Phase》属渗流解析界；本题是反例几何与穷举验证，方向不同。

3 · 可检验假设

• H1：基础图 n ≤ 5（全部连通图 × 全部横档顶点子集）上猜想成立，且 margin 多项式 P_同层(p)−P_跨层(p) 在 (0,1) 上非负可被符号证明（系数结构或根隔离）。
• H2：加权变体（各边参数独立）在 n ≤ 7 内存在数值反例候选（margin < 0 的参数点），且候选可精确有理复核。

4 · 量化验收标准

1. 方法学校验（硬门槛）：自建精确两点连通概率计算器（边子集枚举/删缩 + 有理数算术）复现 (a) K₄ 的两点连通多项式已知表达式；(b) 串并联小图的手算值 ≥ 8 例；并与 10^7 次蒙特卡洛对比，全部差 < 3σ。不吻合则后续无效。
2. n ≤ 5：全部连通图（21 个）× 全部非空横档子集的 margin 多项式表，每条给出非负性证明或反例点；符号结论与 p = 0.1,…,0.9 数值网格交叉一致。
3. n = 6, 7：均匀 p 网格 + 加权参数随机搜索（≥ 10^5 参数点/图，报告覆盖策略），所有 margin < 10^-6 的候选一律精确有理复核。
4. 汇总"最小 margin vs 图参数"结构分析（哪类图最接近违反猜想），为后续构造提供数据。
5. 蒙特卡洛部分报标准误与置信区间；全部代码与 margin 数据开源。

5 · 数据与工具

用途	来源 / 工具
精确连通概率	Python 自写删缩（deletion–contraction）+ 割点分解 + 同构缓存；需自行实现。n = 5 基础图的双层床图 ≤ 25 边，最坏 2^25 但缓存后实际远小——第 6 周实测定标
符号多项式	sympy / fractions（有理系数精确；根隔离用 sympy real_roots）
数值搜索	numpy 蒙特卡洛 + 局部下降（对加权参数）
图生成	networkx atlas（n ≤ 7 内置）；nauty geng 备选
已有结果对照	GPZ 反例、森林/完全图定理、粘合引理——仅校验与对比用，不计入贡献；粘合引理可用于剪掉可约图，缩小穷举面

6 · 方法路径

1. 实现精确连通概率计算器，完成校验（含蒙特卡洛对照）。
2. 用顶点粘合引理与森林定理剪掉可约/已证图类，确定必检图清单（把已有定理转化为搜索空间约简）。
3. 跑 n ≤ 5 全表，符号证明每条 margin 非负性。
4. n = 6, 7 数值网格 + 加权随机搜索，候选精确复核。
5. 分析最小 margin 的图结构特征，与 GPZ/Hollom 构造的结构要素（多路复用 gadget）比对。
6. 独立交叉校验：抽样实例用状态 DP（按顶点割的连通划分传递）第二实现复算。

7 · 新颖性边界

猜想的证伪（GPZ 2024/2025）、成立类定理（完全图、森林、轮图）、粘合引理均为已发表结果；本项目不声称重新解决猜想真伪。贡献（主结论）：最小反例规模的首个系统下界数据——n ≤ 5 的符号排除 + n ≤ 7 加权变体搜索 + margin 结构分析。价值：GPZ 明确留下"最小反例多大"与"加权版本更易违反"两个公开问题，本项目直接给出其小规模一侧的可复核答案；"无小反例"配 margin 误差棒即为有效负结论。

8 · 决策门槛（go / no-go）

• 第 6 周末：删缩计算实测。若 n = 5 单实例 > 1 h → 降级一：换连通划分 DP（复杂度随割宽而非边数），或上限收缩为"n ≤ 4 符号 + n = 5 数值"，主结论框架（边界数据）不变。
• 第 14 周末：若加权搜索无任何 margin < 10^-3 的候选 → 降级二：转向独立精确复算 Hollom 超图反例并做其最小化（超图规模小，精确可算——规模数据第 14 周核实），主题仍为"最小反例边界"。
• 第 26 周末：冻结搜索，无论正负进入结构分析与写作。
• 选择前提：本题是 10 题中风险最高者——上限（小反例）为顶刊级、概率极低；基线产出（符号验证表 + margin 分析）足以成文但理论浓度高。仅推荐给概率与编程双强、且书面接受"基线即负结果"的学生；预算裁剪顺序：先砍 n = 7 加权搜索，再砍 n = 6，符号表为不可砍核心。