九 章 格 数 学 · 数 学 前 沿 · V I P 专 阅

萨姆纳通用竞赛图猜想

《图论中的 50 个公开问题》 · 问题 28 专题综述

题面每个 2n−2 个顶点的竞赛图都包含任意 n 点有向树吗?

本页为 VIP 专阅综述:主要概念的详细介绍与主要命题的细致证明,全文见下方专阅区。

问题

萨姆纳 1971 猜想:每个有 2n−2 个顶点的竞赛图(任意两点恰一向的有向完全图)都包含任意给定的 n 个顶点的有向树作为子图。常数 2 已被 «双向星» 类例子证明最优(星形有向树的 «叶必须全向» 要求迫近 2n)。

主要概念

无向版的对照

无向情形是 Grünbaum 定理(平凡:竞赛图 «去掉方向» 是完全图,什么树都装得下——有向才是难点:树的边有方向,竞赛图必须 «顺着» 提供)。困难例:出度全为 ⌈(n−1)/2⌉ 的 «均匀» 竞赛图装 «大出度星» 树很紧——树根需 n−1 条 «出边邻居»,竞赛图最大出度可能只有 n−1,恰好不够富余。

近似证明的骨架

Bucić–Letzter–Sudakov 2021 证明 2n + o(n) 版本:把树按 «叶块» 分层,竞赛图按 «出度分层» 分块; «块对块» 的 «嵌入引理»(大出度层装叶块、其余层装骨架)逐一安放。 «Q-树»(允许 «块» 是双向完全子图的树)被完全覆盖。

主要命题与证明

命题 1(下界构造完整证明) 存在 2n−3 个顶点的竞赛图不含某个 n 点有向树——常数 2 不可降。

证明 取 «双向星» T:n−1 个叶都从根指出(出星)。构造竞赛图 R:n−1 个 «红» 点对剩下 n−2 个 «蓝» 点 «全指蓝»(红→蓝),红内部、蓝内部任取。装 T:根必须指向 n−1 个叶;若根是红点,其出邻居 ⊆ 红内(≤ n−2 个)∪ 蓝(但红→蓝指 «蓝的入边» 方向——检查:R 中红→蓝,故红点的出邻居只在红内 ≤ n−2 < n−1,装不下);若根是蓝点,出邻居 ⊆ 蓝内 ≤ n−2 < n−1。故 T ⊄ R,而 |V(R)| = 2n−3。□

命题 2(BLS 近似定理骨架) 每个 2n + C log n 顶点的竞赛图包含每个 n 点有向树。核心嵌入引理: «大入度 » 点集能装 «叶向外» 的块, «大出度» 装反向块,中间 «平衡层» 用贪心匹配串联。剩余 log 项来自 «层间衔接» 的浪费——猜想的最后一步正是把浪费压到 0。

进展与文献

Sumner 1971 原猜想(与 «通用有向图» 纲领同期);Havet–Thomassé 的早期部分结果(出度受控的竞赛图情形);Bucić–Letzter–Sudakov 2021(2n+o(n),Annals 系)与其 «Q-树» 技术。开放核心:精确常数 2 的 «零浪费» 嵌入——现有技术的层间损耗机制上似乎 «不可压»,需全新 «全局安放» 视角;离散几何与组合优化的交界样本。

← 返回问题 28