A note on Ramsey numbers for minors

この論文は、ハドウィガー数が$k$となる単色部分グラフを含むための完全グラフの最小頂点数（ラムゼー数）$R_h(k; \ell)$について、2 色の場合の上下界および一般の$\ell$色における漸近挙動を決定したことを報告しています。

要約

色のパズルと「縮める」魔法：ラムゼー数の新しい発見

この論文は、数学の「グラフ理論」という分野における、少し変わったパズルについて語っています。専門用語を避け、日常の比喩を使って、何が書かれているのかをわかりやすく解説します。

1. 基本のゲーム：「色」のついた完全なネットワーク

まず、想像してみてください。
街中に $n$ 人の人がいて、そのすべての人同士が手を取り合っている（全員が友達である）とします。これを「完全グラフ」と呼びます。

ここで、この手を取り合う関係（エッジ）に、赤と青の 2 色のペンキを塗るゲームを始めます。

• 古典的なルール（ラムゼー数）: 「同じ色の三角形（3 人のグループ）が必ずできる最小の人数 $n$ は？」という問題です。
• この論文の新しいルール: 「同じ色のグループの中で、『縮める』魔法を使って、$k$ 人のグループ（完全な $k$ 人組）を作れる最小の人数 $n$ は？」という問題です。

「縮める」魔法とは？

ここで重要なのが「ハドウィガー数（Hadwiger number）」という概念です。

• 通常のルール: グループ内の全員が直接手を取り合っている必要があります。
• この論文のルール: 直接手を取り合っていなくても、**「2 人の手をまとめて 1 人のように扱う（辺の縮約）」や「そのグループから人を抜く（頂点の削除）」**という操作を繰り返して、結果的に $k$ 人が全員で手を取り合っている状態にできれば、それは「$k$ 人のグループが見つかった」とみなします。

まるで、粘土細工のように、複数の塊をくっつけたり削ったりして、最終的に「完全な $k$ 人組」の形を作れるかどうかを問うゲームです。

2. この研究が解いたこと

著者のマリア・アクセノビッチさんは、この「縮める魔法」を使ったゲームにおいて、**「必要な人数（$n$）と、目標とするグループの大きさ（$k$）の間に、どんな関係があるか」**を突き止めました。

発見の核心：対数（ログ）の不思議な関係

結論はシンプルに言うとこうです。
「目標のグループの大きさ $k$ が大きくなると、必要な人数 $n$ は、$k$ の**『対数（ログ）』**をかけたような形で増えます。」

• イメージ: $k$ が 2 倍になっても、必要な人数は 2 倍にはなりません。もっと緩やかに増えます。
• 数式での表現: $n \approx k \times \sqrt{\log k}$
  • 左側の「下限」：これより少ない人数では、どんなに頑張っても $k$ 人組は作れない。
  • 右側の「上限」：これくらいの人数いれば、どんな塗り方をしていても、必ず $k$ 人組が見つかる。

著者は、この「上限」の値を、従来の推定よりも少しだけ正確に（1.031 倍という係数で）計算し直しました。また、色の種類（$\ell$ 色）が増えると、必要な人数は色数に比例して増えることも示しました。

3. 具体的な例え話

例え話：巨大なパーティーと「縮小版」のチーム

巨大なパーティー（$n$ 人）があり、参加者同士は全員が知り合いです。

• 赤い服を着ている人同士、青い服を着ている人同士をそれぞれグループにします。
• 目標は、「赤い服の人たちの中から、縮小魔法を使って 5 人組（$k=5$）の完全なチームを作る」ことです。

もし参加者が 100 人しかいないなら、赤い服の人たちがバラバラすぎて、どんなに縮めても 5 人組は作れないかもしれません。
しかし、参加者が 1000 人、1 万人と増えると、赤い服の人たちの間には「つながり」が溢れ、縮める魔法を使えば、必ず 5 人組（あるいはそれ以上）のチームが作れるようになります。

この論文は、**「5 人組を作るために、最低でも何人のパーティーが必要か？」**という答えを、より精密に導き出しました。

なぜこれが重要なのか？

• ハドウィガー予想との関係: 数学には「ハドウィガー予想」という有名な未解決問題があります。「グラフの複雑さ（色を塗るのに必要な色数）と、縮めて作れるグループの大きさには関係がある」というものです。この論文は、その「縮めて作るグループ」の大きさを、ランダムな色付けという視点から研究した初めての試みの一つです。
• ランダム性の力: 論文では、「ランダムに色を塗った場合（サイコロを振って決めた場合）」が、最も「グループが作りにくい」状態であることを利用しています。つまり、「ランダムな状態でもこれだけあれば作れるのだから、どんな状態でも作れる」という論理を使っています。

4. まとめ

この論文は、**「複雑なネットワークの中で、縮める魔法を使って特定の形（完全なグループ）を見つけるには、どれだけの規模が必要か」**という問いに、数学的に厳密な答えを出したものです。

• 発見: 必要な人数は、$k \sqrt{\log k}$ という形に比例する。
• 意義: 従来の「直接つながっている」ルールだけでなく、「縮めてつなぐ」という柔軟なルールでも、ネットワークの性質がどう振る舞うかがわかった。

まるで、巨大な迷路の中で「縮小レンズ」を使って出口を見つけるゲームにおいて、「迷路の広さがこれくらいあれば、どんなに複雑な道順でも、縮小レンズを使えば必ず出口が見つかる」という保証を得たようなものです。

数学的には非常に高度な計算（確率論やグラフ理論の深い部分）が使われていますが、その核心は**「ネットワークの規模と、そこから特定の形を抽出する難しさのバランス」**を、より正確に測る新しい物差しを作った点にあります。

技術概要

論文「A note on Ramsey numbers for minors」の技術的サマリー

1. 概要と問題設定

本論文は、グラフ理論における**ラムゼイ数（Ramsey number）**の一種である、マイナー（minor）に関するラムゼイ数 $R_h(k; \ell)$ の漸近的な評価について論じています。

• 問題定義: $R_h(k; \ell)$ を、$n$ 頂点の完全グラフ $K_n$ の辺を $\ell$ 色で彩色したとき、必ず単一色の部分グラフが存在し、その部分グラフの**ハドウィガー数（Hadwiger number）**が $k$ 以上となるような最小の整数 $n$ として定義します。
  • ハドウィガー数 $h(G)$ は、グラフ $G$ から辺の縮約（edge contractions）と頂点の削除（vertex deletions）を繰り返すことで得られる最大完全グラフ $K_k$ のサイズ $k$ です。
  • 古典的なラムゼイ数 $R(k)$ は、単一色の部分グラフが $K_k$ 自身（完全グラフ）を含む場合ですが、本論文では「$K_k$ をマイナーとして含む」というより緩やかな条件を扱っています。
• 背景: ハドウィガー予想（$h(G) \ge \chi(G)$）や、グラフの密度とハドウィガー数の関係（Thomason の結果など）はよく研究されていますが、マイナーに関するラムゼイ数 $R_h(k; \ell)$ 自体は、これまで明示的に扱われていなかったようです。

2. 主要な結果（定理）

定理 1.4: 2 色のケース ($\ell=2$)

$R_h(k) = R_h(k; 2)$ について、以下の漸近的な評価が得られました。
$$k\sqrt{\log k}(1 + o(1)) \le R_h(k) \le 1.031 \cdot k\sqrt{\log k}(1 + o(1))$$

• 定数の精度: 上界の定数は $1.031$であり、これは Thomason の密度に関する結果を用いた単純な推定（約$1.062$）よりも改善されています。
• 小値の厳密値:
  • $R_h(3) = 5$
  • $R_h(4) = 7$
  • $k \ge 5$ に対して、$2(k-2) \le R_h(k) \le 32(k-2)^{\lfloor \log(k-2) \rfloor} + 1$ という一般的不等式も示されています。

定理 1.5: 多色ケース ($\ell \ge 1$)

色数 $\ell$ が一般の場合、$k$ が十分大きく、かつ $\ell$ も十分大きいとき、以下の漸近式が成立します。
$$R_h(k; \ell) = 2\beta \ell k\sqrt{\log k}(1 + o(1))$$
ここで、$\beta = 0.265656\dots$ は Thomason の結果における定数です。

• 小値の厳密値: $R_h(3; \ell) = 2\ell + 1$ が示されています。

3. 手法と証明の概要

上界の導出

1. 密度と連結性の利用:
   • 任意の彩色において、多数派の色（例えば赤）のグラフ $G$ を考えます。$G$ の辺の数は $n^2/4$ 程度です。
   • Thomason の定理 (Theorem 1.3) を利用します。この定理は、連結性が十分高いグラフにおいて、ハドウィガー数が密度から推定できることを示しています。
   • ケース分け:
     • ケース 1: $G$ の連結性が高い場合、Thomason の定理を直接適用し、$h(G) \ge k$ を示します。
     • ケース 2: 連結性が低い場合、最小の頂点カット $X$ を考えます。最小次数の条件から、$G-X$ の各連結成分のサイズが $k$ 以上であることが導かれます。これにより、補グラフ（青）に $K_{k,k}$ が存在し、青の $K_k$-マイナーが存在することを示します。
   • 定数の改善: 単純な密度論（Thomason の定理 1.1 のみ）では定数 $2\sqrt{\beta} \approx 1.062$になりますが、連結性の議論と部分グラフの再帰的な構造を精密に分析することで、定数を$1.031$ まで改善しています。

下界の導出

1. 確率的構成:
   • $n = k\sqrt{\log k}(1-\epsilon)$ なる $K_n$ を考え、各辺を確率 $1/2$ で赤・青にランダムに彩色します。
   • 各色のグラフは $G(n, 1/2)$ に分布します。
   • Bollobás, Catlin, Erdős の定理 (Theorem 1.2) により、$G(n, 1/2)$ のハドウィガー数は漸近的に $k$ より小さくなることが知られています。したがって、単一色の $K_k$-マイナーが存在しない彩色が確率 1 で存在し、これが下界となります。
2. 多色ケースの下界:
   • $K_k$-マイナーを含まないグラフ $H'$ を構成し、これを $K_n$ にパック（分解）する手法を用います。
   • Wilson の定理やAlon-Yuster の結果を用いて、$K_n$ を $H'$ のコピーに分解し、それぞれに異なる色を割り当てることで、単一色の $K_k$-マイナーを含まない彩色を構成します。

4. 重要な定数 $\beta$ の定義

論文で用いられる定数 $\beta$ は、Thomason がグラフの密度とハドウィガー数の関係を決定する際に導出したものです。

• $\lambda$ は方程式 $1 - \lambda + 2\lambda \ln \lambda = 0$の解（$\lambda < 1$）。
• $\beta = \frac{1-\lambda}{2\sqrt{\ln(1/\lambda)}} \cdot \frac{1}{\sqrt{\log_2 e}} \approx 0.265656$。
• この定数は、$c(k) = \beta k\sqrt{\log_2 k}(1+o(1))$ として、$K_k$-マイナーを含まないグラフの最大辺密度の係数となります。

5. 意義と結論

• 研究の空白の埋め合わせ: ハドウィガー数に関するラムゼイ数という自然な概念が、これまで明示的に研究されていなかった点を指摘し、その漸近的な振る舞いを初めて定式化しました。
• 定数の精密化: 2 色のケースにおいて、上界の定数を $1.062$から$1.031$ へと改善しました。
• 今後の課題: 著者は、定数 $c$ が実際には $1$であると予想しています（$R_h(k; 2) \sim k\sqrt{\log k}$）。密度定理（Thomason の結果）に依存しない、より直接的な証明の構築が今後の課題として挙げられています。

この論文は、極値グラフ理論（Extremal Graph Theory）とラムゼイ理論の交差点において、マイナーという構造を捉えるための新しい視点と精密な評価を提供する重要な貢献です。