Acyclic Dichromatic Number of Tournaments: these are the Champions

技术摘要：竞赛图的无环双色数

问题陈述
本文研究了定向图（特别是竞赛图背景下）的无环双色数 ($\vec{\chi}_a$)。一个无环 $k$-双着色是将顶点集划分为 $k$ 个集合，使得任何单个部分诱导的子有向图都是无环的，且任意两个部分之间的定向二部图也是无环的。无环双色数是实现此类划分所需的最小 $k$ 值。

作者探讨了由 Bang-Jensen, Picasarri-Arrieta 和 Yeo [4] 提出的两个特定猜想：

1. 冠军特征化（Characterization of Champions）： 识别哪些竞赛图 $H$ 是“冠军”（类似于标准双色数理论中的“英雄”），即每个不含 $H$ 的竞赛图都具有有界的无环双色数。
2. 局部-全局性质（Local-to-Global Property）： 确定竞赛图的无环双色数是否受其顶点出邻域的最大无环双色数之函数的限制。

方法论
本文利用结构图论和 Ramsey 型论证来建立无环双色数的界限。

• 维匹配（Dimatchings）： 文中引入的一个核心工具是维匹配，定义为一组两两不相交的弧 $\{a_1b_1, \dots, a_kb_k\}$，满足当 $i=j$ 时 $a_i \to b_j$，当 $i \neq j$ 时 $a_i \leftarrow b_j$。作者利用 Bang-Jensen 等人 [4] 的一个结果，即存在大型维匹配意味着具有高的无环双色数。
• Ramsey 理论： 证明过程利用了 Erdős-Moser 定理 [8]，即在大规模竞赛图中存在传递子竞赛图的结论，从而在包含大型维匹配的竞赛图中定位特定的结构配置（具体为竞赛图 $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$）。
• 归约为二部图： 为了证明具有高无环双色数的竞赛图中存在大型维匹配，作者将问题归约为二部图的性质。他们利用了 Atminas [2] 关于二部图中诱导匹配和共匹配的研究结果。具体而言，他们将二部竞赛图的无环双色数与底层无向二部图中不存在诱导 $2K_2$（大小为 2 的诱导匹配）的关系联系起来。
• 递归划分： 证明过程涉及将竞赛图分解为传递集，并使用基于引理 9（该引理通过诱导子图限制有向图的无环双色数）得到的推论来分析这些集合之间的相互作用。

主要贡献与结果

1. 确认冠军猜想（定理 3）：
   作者证明了一个竞赛图 $H$ 是冠军，当且仅当它同构于对于某个整数 $k \ge 1$ 的 $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$ 的一个子竞赛图。

   • 机制： 他们证明了任何具有足够大的维匹配的竞赛图都必须包含一个同构于 $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$ 的子竞赛图。由于大型维匹配强制产生高的无环双色数，因此任何避开这一特定结构的竞赛图都具有有界的无环双色数。

2. 维匹配的存在性（定理 4）：
   本文建立了一个函数 $f: \mathbb{N} \to \mathbb{N}$，使得每个无环双色数至少为 $f(k)$ 的竞赛图都包含一个大小为 $k$ 的维匹配。

   • 机制： 该结果依赖于 Atminas 关于二部图的定理 [2]。通过展示如果一个竞赛图缺乏大型维匹配，其结构可以被划分为具有特定二部相互作用的有界数量的传递集，作者从而限制了无环双色数。

3. 确认局部-全局性质（定理 5）：
   作者证明了存在一个函数 $g: \mathbb{N} \to \mathbb{N}$，使得对于任何竞赛图 $T$，$\vec{\chi}_a(T) \le \max_{v \in V(T)} g(\vec{\chi}_a(v^+))$。

   • 机制： 这是作为定理 4 的推论得出的。如果一个竞赛图具有较大的无环双色数，它就包含一个大型维匹配。该维匹配的结构确保了某些顶点的出邻域包含一个大型维匹配，从而迫使局部邻域具有高的无环双色数。

意义与主张
本文证实了 Bang-Jensen, Picasarri-Arrieta 和 Yeo [4] 的两个猜想，从而完成了对无环双色数“冠军”的特征化，并确立了其局部-全局性质。

作者指出，虽然冠军特征化的前向蕴含关系（即冠军必须具有特定形式）此前已知，但其逆命题（即具有此形式的竞赛图确实是冠军）是本研究的创新贡献。此外，论文在附录中提供了定理 3 的另一种证明，该证明不依赖于定理 4 或 Atminas 的结果，作者认为这种方法能产生更好的上界，并可能对未来的研究具有独立价值。

这项工作弥合了已被充分理解的双色数（其中“英雄”被归纳为一种特定的递归结构）与更具限制性的无环双色数之间的差距，表明尽管两者结构不同，但在竞赛图中，有界性和局部性这两个基本性质对于这两个参数均成立。