Anti-Ramsey Numbers for Spanning Linear Forests of 3-Vertex Paths and Matchings

本論文は、すべての $k \ge 1$ および $t \ge 2$ に対して、$n=3k+2t$ なる $k$ 個の互いに素な 3 頂点パスと $t$ 個の互いに素な辺からなる全域線形森林のアンチ・ラムゼイ数を決定し、それによって先行研究における制限を伴わない形でこの問題を解決する。

要約

巨大なパーティーを想像してください。参加者の総数を$n$とします。このパーティーでは、すべての参加者が他のすべての参加者とちょうど一度だけ握手をします。数学的には、これは「完全グラフ」（$K_n$）と呼ばれます。

さて、あなたはパーティーの企画者であり、大量の色付きマーカーの箱を持っていると想像してください。あなたの仕事は、すべての握手（辺）を特定の色で塗ることです。パーティーをできるだけカラフルにしたいのですが、厳格なルールがあります：特定の「虹のパターン」を作らないようにしなければならないというルールです。

禁止されるパターン

あなたが避けようとしているパターンは、小さな非連結な人々の集まりの集合です：

1. 3 人のグループ $k$ つが一直線に並んでいるもの（3 頂点のパス、または $P_3$）。
2. 2 人のペア $t$ つが一緒に立っているもの（2 頂点のマッチング、または $P_2$）。

「虹の」パターンとは、これらの特定のグループ内のすべての握手が、グループ内の他のすべての握手とは異なる色で塗られていることを意味します。もしパターン内の握手が 2 つでも同じ色を共有していれば、そのパターンは「壊れて」おり、あなたは安全です。

大きな問い

この論文が問うているのは：この禁止された虹のパターンを偶然作り出さずに、パーティーのすべての握手を塗るために使用できる異なる色の最大数はいくつでしょうか？

数学の世界では、この最大数は反ラムゼー数と呼ばれます。

過去の苦闘

長い間、数学者たちはこの問いに対する答えを知っていましたが、非常に厳格な条件下でのみでした。まるで、「ペアの数（$t$）がトリプレットの数（$k$）に比べて巨大であれば、答えは分かっている」と言っているようなものです。具体的には、以前の研究では $t$ が $k$ のおおよそ 2 乗（二次の関係）であることが要求されていました。$t$ がそれより小さい場合、数学は機能せず、答えは不明でした。

新しい発見

この論文は、最も重要かつ厄介なシナリオである**「スパンニング」ケース**の謎を解きました。

「スパンニングケース」とは、パーティーが完全に満員になった瞬間と考えることができます。参加者の総数（$n$）は、禁止されたパターンを形成するために必要な人数と正確に等しくなります：

• $n = 3 \times (\text{トリプレットの数}) + 2 \times (\text{ペアの数})$
• $n = 3k + 2t$

著者であるアリ・ガラヴァンドと李学良は、$t$ が巨大である必要はもはやないことを証明しました。少なくとも 1 つのトリプレット（$k \ge 1$）と少なくとも 2 つのペア（$t \ge 2$）があれば、彼らは最大の色数の正確な式を見つけ出しました。

式

この論文は、使用できる色の最大数は以下の通りであると主張しています：
$$\frac{1}{2}(3k + 2t - 3)(3k + 2t - 4) + 1$$

これを平易な英語で言うとどうなるでしょうか？
もしこの数より1 つ多い色を使おうとすれば、数学的に禁止された虹のパターン（すべてが一意の色を持つ $k$ 個のトリプレットと $t$ 個のペア）を偶然作り出してしまうことが保証されます。しかし、この数以下に留めれば、パターンが現れないように色を配置することができます。

彼らがどのように証明したか

著者たちは、巧妙な「分割統治」戦略を用いました。彼らはこれを 16 の異なるシナリオに分解しました（色の配置可能なすべての方法をチェックするようなものです）：

1. 下限（「安全」な方法）： 彼らは、パターンを作らずに式の数の色でグラフを塗る方法を示しました。パーティーの大きな塊を取り出し、それをすべて一意に色付けし、残りのすべての握手をたった1 つの新しい色で塗ると想像してください。これにより、追加の握手が同じ色を共有するため、潜在的な虹のパターンは破壊されます。
2. 上限（「危険」な方法）： 彼らは、1 つでも多くの色を使おうとすれば、パターンを作らざるを得ないことを証明しました。そのために、パターンを作らなかったと仮定し、それが数学的に矛盾（丸い穴に四角い杭を押し込もうとするようなもの）につながることを示しました。彼らは「追加の」ゲスト（メインのグループに含まれない 3 人）の間で色がどのように分配されうるか、あらゆる可能性を分析し、何があっても最終的にパターンが現れることを示しました。

結論

この論文は、「二次の下限」という制限を取り除きました。それは、パーティーのサイズが禁止されたパターンのサイズと正確に一致する特定のケースにおいて、答えはトリプレットやペアの数に関係なく、シンプルで普遍的であることを示しています。これは、グラフ理論の分野における特定の難問に対する完全な解決策です。

技術概要

技術的概要：3 頂点パスとマッチングの全域線形森に対するアンチ・ラムゼー数

問題の定義
本論文は、完全グラフ $K_n$ における特定の線形森のクラスに対するアンチ・ラムゼー数 $AR(n, G)$を調査する。部分グラフがすべての辺に異なる色を有する場合、その部分グラフを「レインボー」と定義する。アンチ・ラムゼー数$AR(n, G)$は、$G$のレインボーなコピーを含まない$K_n$ の辺彩色における最大の色数である。

本研究の対象とする特定のグラフ $G$ は、長さ 2（3 頂点）の $k$ 個の互いに素なパスと、サイズ $t$ のマッチング（互いに素な辺）からなる線形森 $kP_3 \cup tP_2$ である。主な焦点は、ホストグラフの頂点数が森の頂点数と等しい、すなわち $n = 3k + 2t$ となる「全域の場合」である。先行研究では $k \ge 2$ に対して $t$ に関する制限条件（具体的には $t \ge \frac{k^2-3k+4}{2}$）の下でこの問題が扱われていたが、本研究は $k$ と $t$ の関係に関する追加の制約なしに、すべての $k \ge 1$ および $t \ge 2$ に対する全域の場合の解決を目指す。

手法
主要定理の証明は、帰納法と辺彩色の詳細な場合分けの組み合わせに依存する。手法は以下のように構成されている。

1. 帰納的枠組み: 証明は $k$ に関する帰納法によって進められる。基本ケース $k=1$ は、He と Jin による $AR(n, P_3 \cup tP_2)$ に関する既知の結果を用いて確立される。
2. 主要補題（補題 2.2）: 帰納ステップを処理するための決定的な補題が確立される。この補題は、$K_n$ の辺彩色が十分な数の色（具体的には $\frac{1}{2}(3k+2t-3)(3k+2t-4)+2$）を含んでいる場合、3 つの頂点を除去して得られる部分グラフ $K_{n-3}$ が、少なくとも $\frac{1}{2}(3(k-1)+2t-3)(3(k-1)+2t-4)+2$ の異なる色の高い密度を保持することを主張する。これにより、帰納仮説を適用して $K_{n-3}$ 内でレインボーな $(k-1)P_3 \cup tP_2$ を見つけることが可能になる。
3. 網羅的なシナリオ分析: 帰納を完了するために、著者らは除去された頂点 $S = \{s_1, s_2, s_3\}$ とグラフの残りの部分とを結ぶ辺、および $S$ 内の辺に割り当てられた色を分析する。証明は $K_{n-3}$ 内にレインボーな $(k-1)P_3 \cup tP_2$ が存在すると仮定し、集合 $S$ の辺の色分布と既存のレインボー部分グラフの色との交差に基づいて 16 の異なるシナリオを検証する。
   • これらのシナリオは、$S$ 内の辺が新しい色を導入するか、既存の部分グラフから色を繰り返すか、あるいは既存の構造と組み合わせ可能な特定のレインボーパス（$P_3$）やマッチング（$P_2$）を形成するかといった、さまざまな構成を網羅している。
   • 各シナリオについて、著者らは総色数が提案された上限を超えている場合、レインボーな $kP_3 \cup tP_2$ を構築できることを示す。
   • もしそのような構築が即座に不可能な場合、著者らはレインボー部分グラフを形成するための特定の条件が満たされていないと仮定した下での $K_n$ における最大可能な色数を計算することで矛盾を導き出す。すべての場合において、この上限は仮定された色数よりも低くなるため、レインボー部分グラフが存在しなければならないことが証明される。

主要な貢献と結果
本論文は、全域線形森 $kP_3 \cup tP_2$ に対するアンチ・ラムゼー数の正確な値を確立する。

定理 1.1: 正の整数 $k \ge 1$, $t \ge 2$, および $n = 3k + 2t$ に対して：
$$AR(n, kP_3 \cup tP_2) = \frac{1}{2}(3k + 2t - 3)(3k + 2t - 4) + 1$$

この結果は、レインボーな $kP_3 \cup tP_2$ を含まない $K_n$ の彩色における最大の色数が、$n-3$ 頂点の完全グラフの辺数よりちょうど 1 多いことを確認する。本論文は、$K_{n-3}$ 部分グラフを異なる色で彩色し、残りのすべての辺に単一の新しい色を割り当てるという一致する下限の構成を提供し、上記で記述された網羅的な場合分けを通じて上限を証明する。

意義
この研究の意義は、先行研究で必要とされていた $t$ に関する二次的下限の除去にある。具体的には、著者 2 名による先行結果（参考文献 [11]）は、$t \ge \frac{k^2-3k+4}{2}$ の場合のみこの数を決定していた。本論文は、$k$ の大きさに関わらず、すべての $t \ge 2$ に対してこの式が成り立つことを示している。

著者らはこれを、「ホストグラフが森と正確に同じ数の頂点を持つ臨界ケースに対する完全な特徴付け」として位置づけている。パス成分とマッチング成分の比率に関する制限なしに全域の場合を解決することで、本論文は線形森に対するアンチ・ラムゼー数の理解における重要なギャップを埋めた。著者らは、残された未解決問題は、$t$ が小さい場合の非全域の場合（$n \ge 3k + 2t + 1$）に対する結果の改善であると指摘している。