M24
五阶禁图的饱和数：机器穷举求精确值与线性公式证明
来源说明：本则出自独立撰写的第二批方案。它与前 20 则同样遵循八块结构与硬门槛要求，但撰写时未做英文文献检索，新颖性边界依据的是历届获奖图谱与既有知识，而非当轮查新。因此其「需核实」条目更多，启动前须自行补一轮英文检索。
1 · 研究问题
对若干饱和数（saturation number）sat(n, F) 尚无精确公式的 5 阶禁图 F，sat(n, F) 在 n ≤ 11 的精确值是多少？由此猜出的线性公式 sat(n, F) = an + b 能否对所有充分大 n 给出完整证明（上界构造 + 下界论证）？
2 · 研究背景与空白
图 G 称为 F-饱和的，若 G 不含 F 但加任何一条边都产生 F。饱和数 sat(n, F) 是 F-饱和图的最小边数——它是 Turán 数（最大边数）的对偶，由 Erdős–Hajnal–Moon 1964 年对完全图确定：sat(n, Kₚ) = (p−2)n − C(p−1, 2)。Kászonyi–Tuza 证明了 sat(n, F) = O(n) 对一切 F 成立，因此"猜线性公式再证明"是结构上合理的路线。
已有工作：完全图、路、星、若干小图的饱和数已有精确公式；饱和数动态综述（需核实：搜索关键词 saturation numbers of graphs dynamic survey Faudree Gould）维护着已知/未知清单，其中 5–6 阶小图仍有未决情形。丘奖相邻获奖论文：2022 银奖《A Turán-Type Problem in Mixed Graphs》做的是 Turán 方向（最大化），饱和方向（最小化）在获奖清单中未出现。
空白在：动态综述中 5 阶图的未决条目——每一条都是"精确值 + 线性公式"颗粒度的独立小问题，穷举可在笔记本上做到 n = 10–11 提供猜想依据，证明用初等构造与局部结构分析即可。学生课题的合适之处：上界构造给出即为定理的一半，下界即使只对特定 n 完成也是有效部分结果。
3 · 可检验假设
- H1：所选 2–3 个未决 5 阶图 F 的 sat(n, F) 在 6 ≤ n ≤ 11 上呈现稳定线性差分（sat(n+1) − sat(n) 恒定），可提出显式公式。
- H2：其中至少 1 个 F 的公式可完整证明（上界：显式饱和图族构造；下界：最小度与局部结构分析）。
4 · 量化验收标准
- 方法学校验（硬门槛）：穷举管线先复现三个已知精确值——sat(n, K₃) = n − 1、sat(n, K₄) = 2n − 3、以及一个已发表的路/星公式，在 n ≤ 10 全部吻合。不过关则全线无效。
- 精确值交付：每个目标 F 给出 n ≤ 10 的 sat(n, F) 精确值（n = 11 为目标线），并给出达到最小值的全部极值图（同构消重）。
- 证明交付：至少 1 个 F 的完整公式证明；写明其余 F 哪些只有猜想 + 穷举证据。
- 穷举正确性：极值图逐一机器验证"F-自由 + 加任意边即含 F"两条性质，零违例。
- 代码 + 极值图库开源，一键复跑。
5 · 数据与工具
| 用途 | 来源 / 工具 |
|---|---|
| 图生成 | nauty geng（按边数上限裁剪生成：只生成边数 ≤ 当前最优值的图，n = 11 由此可行） |
| 子图判定 | 自写 F-子图检测（5 阶图可硬编码）+ igraph subisomorphic 交叉验证 |
| 未决清单 | 饱和数动态综述（Electronic Journal of Combinatorics，免费；需核实最新版年份） |
| 已知公式对照 | Erdős–Hajnal–Moon 与综述表格（仅校验，不计入贡献） |
| 算力量级 | geng 带边数裁剪后 n = 10 约 10⁶–10⁷ 图、n = 11 约 10⁸ 级，笔记本数天 |
6 · 方法路径
- 搭 geng + F-检测管线，完成第 4 块第 1 条三项复现。
- 文献窗口：核对动态综述最新版，锁定 2–3 个未决 5 阶 F（能力边界核实步）。
- 逐 n 穷举 sat(n, F)（边数从下往上扫，命中即停），产出精确值表与极值图库。
- 观察极值图结构，提出线性公式与构造族。
- 证明上界（构造族验证饱和性）与下界（对最小度分类讨论；必要时借鉴综述中同型图的证明技术）。
- 独立交叉校验：igraph 子图判定复算全部极值图；公式与 n ≤ 11 数值零偏差。
7 · 新颖性边界
- 本课题不声称改进 Kászonyi–Tuza 一般上界，不把已有精确公式（完全图、路、星等）计入贡献。
- 已有工作：饱和数动态综述维护的已知公式清单（第 3 周核实到条目级）；Erdős–Hajnal–Moon 1964 完全图公式。丘奖相邻获奖论文：2022 银奖《A Turán-Type Problem in Mixed Graphs》——本题差异：极值方向相反（饱和最小化 vs Turán 最大化）、图类不同（简单图 vs 混合图）、交付是具体小图的精确值与公式证明。
- 本项目贡献（主结论）：未决 5 阶图的 sat 精确值表 + 至少一条完整证明的新公式 + 极值图结构刻画。
- 价值：动态综述型领域认可"填表 + 证明"贡献，结果可直接被综述收录引用；正负（公式成立/出现非线性异常）都是有效结论。
8 · 决策门槛（go / no-go）
- 第 3 周末：动态综述核对完成，锁定目标 F 清单。若 5 阶未决条目已被清空（可能性低）→ 转 6 阶图或饱和谱（saturation spectrum）问题，管线复用。
- 第 6 周末：硬门槛三项复现通过。
- 第 12 周末：n ≤ 10 精确值表完成。若 n = 10 穷举超 7 天 → 收紧边数裁剪或降为 n ≤ 9，公式猜想依据仍够。
- 第 28 周末：若所有目标 F 的下界证明都卡住，降级路径：主结论改为"精确值表 + 上界构造定理 + 下界的穷举验证（n ≤ 11）"——上界构造本身是严格定理，框架不变。
- 预算裁剪顺序：第 3 个 F → n = 11 层 → 极值图结构章节。