Acyclic Dichromatic Number of Tournaments: these are the Champions

技術的要約：トーナメントにおける非巡回的二彩色数

問題提起
本論文は、向きグラフ（oriented graphs）、特にトーナメントの文脈における「非巡回的二彩色数」（$\vec{\chi}_a$）を研究している。非巡回的 $k$-二彩色とは、頂点集合を $k$ 個の集合に分割するものであり、各部分に誘導される部分有向グラフが非巡回的であり、かつ任意の2つの部分間の向き付き二部グラフも非循環的であるような分割を指す。非巡回的二彩色数は、このような分割に必要な最小の $k$ である。

著者らは、Bang-Jensen, Picasarri-Arrieta, および Yeo [4] によって提起された以下の2つの予想に取り組んでいる：

1. チャンピオンの特性付け： どのトーナメント $H$ が「チャンピオン」（標準的な二彩色数理論における「ヒーロー」に相当）であるかを特定すること。すなわち、すべての $H$ 除去トーナメント（$H$-free tournament）の非巡回的二彩色数が有界となるような $H$ を特定すること。
2. 局所から大域への性質（Local-to-Global Property）： トーナメントの非巡回的二彩色数が、その頂点の外近傍（out-neighborhood）の最大非巡回的二彩色数の関数によって抑えられるかどうかを決定すること。

手法
本論文は、構造的グラフ理論とラムゼー型の議論を用いて、非巡回的二彩色数の境界を確立する。

• ディマッチング（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] による結果を利用している。
• ラムゼー理論： 証明には、大きなトーナメントの中に特定の構造的構成（具体的には、トーナメント $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$）を見出すための、大きなトーナメントにおける推移的トーナメントの存在に関する Erdős-Moser の定理 [8] を用いる。
• 二部グラフへの還元： 高い非巡回的二彩色数を持つトーナメントにおいて大きなディマッチングが存在することを証明するために、著者らは問題を二部グラフの性質へと還元する。彼らは、誘導マッチングおよび共マッチングに関する Atminas [2] の二部グラフに関する結果を利用している。具体的には、基礎となる無向二部グラフにおける誘導 $2K_2$（サイズ2の誘導マッチング）の不在と、二部トーナメントの非巡回的二彩色数との関係性を利用している。
• 再帰的分割： 証明には、トーナメントを推移的集合へと分解し、補題9から導出された系を用いてそれらの集合間の相互作用を分析するプロセスが含まれる。補題9は、ある有向グラフの非巡回的二彩色数を、その誘導部分有向グラフに基づいて抑えるものである。

主要な貢献と結果

1. チャンピオン予想の確認（定理3）：
   著者らは、ある整数 $k \ge 1$ に対して、トーナメント $H$ がチャンピオンであるための必要十分条件は、$H$ が $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$ の部分トーナメントと同型であることであることを証明した。

   • メカニズム： 十分に大きなディマッチングを持つトーナメントは、必ず $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$ に同型な部分トーナメントを含むことを示している。大きなディマッチングは高い非巡回的二彩色数を強制するため、この特定の構造を回避するトーナメントは、非巡回的二彩色数が有界となる。

2. ディマッチングの存在（定理4）：
   本論文は、非巡回的二彩色数が少なくとも $f(k)$ であるすべてのトーナメントが、サイズ $k$ のディマッチングを含むような関数 $f: \mathbb{N} \to \mathbb{N}$ を確立している。

   • メカニズム： この結果は、二部グラフに関する Atminas の定理 [2] に依拠している。大きなディマッチングを欠くトーナメントの構造は、特定の二部的な相互作用を持つ有界個数の推移的集合へと分割できることを示すことで、著者らは非巡回的二彩色数を抑えている。

3. 局所から大域への性質の確認（定理5）：
   著者らは、任意のトーナメント $T$ に対して、$\vec{\chi}_a(T) \le \max_{v \in V(T)} g(\vec{\chi}_a(v^+))$ を満たす関数 $g: \mathbb{N} \to \mathbb{N}$ の存在を証明した。

   • メカニズム： これは定理4の帰結として導かれる。もしトーナメントが大きな非巡回的二彩色数を持つならば、それは大きなディマッチングを含む。このディマッチングの構造により、特定の頂点の外近傍が大きなディマッチングを含むことが保証され、それによって局所的な近傍における高い非巡回的二彩色数が強制される。

意義と主張
本論文は、Bang-Jensen, Picasarri-Arrieta, および Yeo [4] による2つの予想を解決し、非巡回的二彩色数における「チャンピオン」の特性付けを完了させ、その局所から大域への性質を確立した。

著者らは、チャンピオンの特性付けにおける順方向の含意（チャンピオンは特定の形式を持つ必要があること）は既知であったが、その逆（この形式のトーナメントが実際にチャンピオンであること）が本研究の新規な貢献であると述べている。さらに、付録において、定理4や Atminas の結果に依存しない定理3の代替証明を提供しており、著者らはこれがより良い上界を与え、将来の研究において独立した関心事となり得ることを示唆している。

本研究は、よく理解されている二彩色数（そこでの「ヒーロー」は特定の再帰的構造によって特徴付けられる）と、より制約の強い非巡回的二彩色数の間の溝を埋めるものであり、構造は異なるものの、トーナメントにおける有界性と局所性という基本的な性質は両方のパラメータにおいて保持されることを示している。