$L_2$ Turán Problems for Small Tournaments and Stability

技术摘要：小规模锦标赛的 $L_2$ Turán 问题与稳定性

问题陈述
本文研究了有向图（digraphs）的 $L_2$ Turán 问题。具体而言，旨在确定在避免特定禁向子图 $H$ 的 $m$ 个顶点的有向图中，出度序列的最大可能平方 $L_2$ 范数，记作 $\text{ex}^+_{L_2}(m, H)$。该量定义为：
$$\text{ex}^+_{L_2}(m, H) = \max \left\{ \sum_{v \in V(D)} (d^+_D(v))^2 : |V(D)| = m, D \text{ 是 } H\text{-free} \right\}$$
本研究侧重于小型锦标赛（tournaments），特别是自共轭锦标赛（self-converse tournaments），并将其扩展到这些问题的稳定性版本。这项工作受到超图均匀 Turán 密度与调色板极值问题之间联系的启发，其中辅助有向图上的 $L_2$ Turán 问题是建立紧密密度界限的关键精细化步骤。

研究方法
本研究采用了人类-AI 协作的混合方法，利用 Google DeepMind AI 作为共数学家。研究方法分为三个阶段：

1. 计算探索： 通过大量计算来求解针对特定禁向子图的小规模情形下的最大出度平方和。这些数据被用于对极值结构提出精确的猜想。
2. 结构分析： 作者利用结构图论，包括对称化论证、半完全商图（semicomplete quotients）的分析以及强连通分量（SCCs）的性质。关键工具包括 Camion 定理（关于强连通半完全有向图中的哈密顿圈）和 Moon 定理（关于强连通锦标赛中的子锦标赛）。
3. 代数优化与稳定性： 对于精确结果，作者通过将顶点划分为独立集（扩充/blow-ups）来优化代数公式。对于稳定性结果，他们对出度序列应用全局结构主导论证，利用 Abel 求和及级数消去恒等式来限制近极值图与精确极值构造之间的“结构亏损”。

核心贡献与结果

1. 小型锦标赛的精确 $L_2$ Turán 数
本文解决了关于 $\text{ex}^+_{L_2}(m, H)$ 精确值的三个特定开放问题：

• 传递锦标赛 ($TT_4$)：
  作者证明了完全有向三部 Turán 图 $T_3(m)$ 是该目标函数的唯一最大化结构。

  • 定理 3.1： 对于所有 $m \ge 1$，$\text{ex}^+_{L_2}(m, TT_4) = \|d^+_{T_3(m)}\|^2_2$。
  • 证明策略： 证明过程确立了任何 $TT_4$-free 有向图都可以由一个对应于三部结构的函数 $F(a,b,c)$ 来界定。研究表明，平衡划分大小（使其尽可能相等）会严格增加 $L_2$ 范数，从而导致唯一的极值图 $T_3(m)$。

• 强连通自共轭锦标赛 ($R_4$)：
  $R_4$ 是唯一的具有四个顶点的强连通自共轭锦标赛（出度序列为 1, 1, 2, 2）。

  • 定理 3.2： 极值图唯一同构于结构 $E(m)$。该结构由一个完全三部有向图 $T_3(k)$ 紧随一个传递锦标赛 $TT_{m-k}$ 组成，所有边从 $T_3(k)$ 指向 $TT_{m-k}$。
  • 模运算条件： 参数 $k$ 取决于 $m \pmod 3$：
    • 若 $m \equiv 0, 2 \pmod 3$，则 $k = m$（图纯粹为 $T_3(m)$）。
    • 若 $m \equiv 1 \pmod 3$，则 $k = m-1$。在这种情况下，通过“剥离”一个末端汇点（sink vertex）形成 $T_3(m-1) \to v$，相比于 $T_3(m)$ 能严格增加目标函数值。
  • 本文根据 $m = 3q + r$ 提供了 $\text{ex}^+_{L_2}(m, R_4)$ 的精确代数公式。

• 正则锦标赛 ($Reg_5$)：

  • 猜想 3.3： 基于对小规模 $m$ 的计算证据，作者猜想 Turán 图 $T_4(m)$（完全有向四部图）在 $Reg_5$-free 有向图中唯一最大化 $L_2$ 范数。文中提出了针对 $m = 4q + r$ 的精确代数公式。

2. $\vec{C}_3$-free 有向图的稳定性
本文讨论了有向三角形 $\vec{C}_3$ 的 $L_2$ Turán 问题的稳定性版本。

• 定理 3.4： 若一个具有 $n$ 个顶点的无环 $\vec{C}_3$-free 有向图 $D$ 的出度序列平方和满足 $\sum (d^+(v))^2 \ge \frac{n^3}{3} - \delta n^3$，则 $D$ 到有序双向链 $\vec{F}_{n,2}$ 的编辑距离至多为 $O(\delta^{1/2})n^2$。
• 推论 3.5： 针对调色板密度证明了相应的稳定性结果。如果一个避开 $\vec{C}_3$ 的左、右调色板的 $m$ 色调色板密度至少为 $\frac{1}{3} - \frac{1}{3m^2} - \delta$，则其辅助有向图与有序双向链极值构造的编辑距离在 $O(\delta^{1/2})m^2$ 之内。

意义与主张
本文声称对先前处于开放状态的特定度平方 Turán 问题提供了全面的解决。

• 精确性： 它确定了 $TT_4$ 和 $R_4$-free 有向图的精确最大 $L_2$ 范数平方，解决了近期文献中的开放问题。
• 结构洞察： 它揭示了对于 $R_4$-free 有向图，极值结构并不总是纯粹的 Turán 图；当 $m \equiv 1 \pmod 3$ 时，需要进行特定的“剥离”操作才能实现最大化。
• 稳定性： 它建立了一个 $\vec{C}_3$-free 有向图的定量稳定性定理，证明了近极值图在结构上必须接近有序双向链。
• 方法论展示： 这项工作强调了人类-AI 协作在将计算探索与形式数学证明相结合方面的效能，特别是在为复杂的极值结构生成猜想方面。

作者指出，虽然关于 $Reg_5$ 的结果目前仍是猜想性的，但建立的框架表明，类似的代数简化手段未来可能引导出形式化证明。本文并不声称解决了所有禁向子图的一般性 $L_2$ Turán 问题，而是将重点放在这些特定的微型锦标赛上，作为基础性的步骤。