问题
萨姆纳 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 的 «零浪费» 嵌入——现有技术的层间损耗机制上似乎 «不可压»,需全新 «全局安放» 视角;离散几何与组合优化的交界样本。