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

技術要約：小規模トーナメントにおける $L_2$ トゥラン問題と安定性

問題提起
本論文は、有向グラフ（digraph）における $L_2$ トゥラン問題を調査するものである。具体的には、特定の禁止部分有向グラフ $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\}$$
本研究は、小さなトーナメント、特に自己共役（self-converse）トーナメントに焦点を当て、これらの問題の安定性バージョンへと拡張する。本研究は、ハイパーグラフにおける一様トゥラン密度とパレット極値問題との関連性に動機付けられており、そこでは補助的な有向グラフ上の $L_2$ トゥラン問題が、タイトな密度境界を確立するための重要な精緻化として機能している。

手法
本研究は、Google DeepMind の AI 共数学者を利用した、人間と AI のハイブリッドな協調的アプローチを採用している。手法は以下の3つの段階で進行する：

1. 計算による探索： 禁止される部分有向グラフの小規模なケースについて、出次数の二乗和の最大値を計算するために広範な計算を行った。このデータは、極値構造に関する正確な予想を定式化するために使用された。
2. 構造解析： 著者は、対称化（symmetrization）の議論、半完備商（semicomplete quotients）の解析、および強連結成分（SCC）の性質を含む、構造グラフ理論を用いている。主要なツールには、Camion の定理（強連結半完備有向グラフにおけるハミルトン閉路に関するもの）および Moon の定理（強連結トーナメントにおける部分トーナメントに関するもの）が含まれる。
3. 代数的最適化と安定性： 正確な結果を得るために、著者は頂点を独立集合に分割（ブローアップ）することから導かれる代数的な公式を最適化する。安定性の結果については、出次数列に対する大域的な構造的優越（majorization）の議論を用い、Abel の総和法と入れ子状の恒等式（telescoping identities）を利用して、近傍極値グラフと正確な極値構成との間の「構造的欠損」をバウンドする。

主要な貢献と結果

1. 小規模トーナメントに対する正確な $L_2$ トゥラン数
本論文は、$\text{ex}^+_{L_2}(m, H)$ の正確な値に関する3つの具体的な未解決問題を解決する：

• 推移的トーナメント ($TT_4$):
  著者は、完全有向3部トゥラングラフ $T_3(m)$ が目的関数を一意に最大化することを証明する。

  • 定理 3.1: すべての $m \ge 1$ に対して、$\text{ex}^+_{L_2}(m, TT_4) = \|d^+_{T_3(m)}\|^2_2$ である。
  • 証明戦略: 証明は、任意の $TT_4$-free 有向グラフが、3部構造に対応する関数 $F(a, b, c)$ によって抑えられることを確立する。分割サイズを（できる限り等しく）均衡させることが $L_2$ ノルムを厳密に増加させ、一意の極値グラフ $T_3(m)$ に導くことが示される。

• 強連結自己共役トーナメント ($R_4$):
  $R_4$ は、4頂点を持つ唯一の強連結自己共役トーナメント（出次数列 1, 1, 2, 2）である。

  • 定理 3.2: 極値グラフは、構造 $E(m)$ に一意に同型である。この構造は、完全3部有向グラフ $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$ である。この場合、$T_3(m-1) \to v$ という終端のシンク頂点を「剥ぎ取る（peeling off）」操作が、$T_3(m)$ よりも目的関数を厳密に増加させる。
  • 本論文は、$m = 3q + r$ に基づく $\text{ex}^+_{L_2}(m, R_4)$ の正確な代数公式を提供する。

• 正則トーナメント ($Reg_5$):

  • 予想 3.3: 小規模な $m$ に対する計算的証拠に基づき、著者は、$Reg_5$-free 有向グラフに対してトゥラングラフ $T_4(m)$（完全有向4部グラフ）が一意に $L_2$ ノルムを最大化するという予想を立てている。$m = 4q + r$ についての正確な代数公式も提案されている。

2. $\vec{C}_3$-free 有向グラフに対する安定性
本論文は、有向三角形 $\vec{C}_3$ に対する $L_2$ トゥラン問題の安定性バージョンに対処する。

• 定理 3.4: $n$ 頂点のループを持たない $\vec{C}_3$-free 有向グラフ $D$ が、出次数の二乗 $L_2$ ノルムに関して $\sum (d^+(v))^2 \ge \frac{n^3}{3} - \delta n^3$ を満たすとき、$D$ から順序付きダイゴン・チェイン $\vec{F}_{n,2}$ への編集距離（edit distance）は高々 $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$ 以内にある。

意義と主張
本論文は、以前は未解決であった特定の次数二乗トゥラン問題に対する包括的な解決を提供すると主張している。

• 正確性: $TT_4$ および $R_4$-free 有向グラフに対する正確な $L_2$ ノルム二乗を決定し、近年の文献における未解決問題を解決した。
• 構造的洞察: $R_4$-free 有向グラフについては、極値構造が常に純粋なトゥラングラフであるとは限らず、最大値を達成するためには特定の「剥ぎ取り（peeling）」操作が必要であることを明らかにしている。
• 安定性: $\vec{C}_3$-free 有向グラフに対する定量的な安定性定理を確立し、近傍極値グラフが構造的に（編集距離の観点で）順序付きダイゴン・チェインに近いことを示した。
• 手法の提示: 本研究は、複雑な極値構造に関する予想を生成する上で、計算的探索と形式的な数学的証明を橋渡しする、人間と AI の協調の有効性を強調している。

著者は、$Reg_5$ に関する結果は現在予想の段階であるが、確立された枠組みは、同様の代数的簡約が将来的に形式的な証明につながる可能性を示唆していると述べている。本論文は、すべての禁止されたトーナメントに対する一般的な $L_2$ トゥラン問題を解くことを主張しているのではなく、これら特定の小規模なトーナメントに焦点を当てることで、基礎的なステップとしている。