2025-11-25T07:46:18.118060

Triangle Ramsey numbers of complete graphs

Fox, Tidor, Zhang
A graph is $H$-Ramsey if every two-coloring of its edges contains a monochromatic copy of $H$. Define the $F$-Ramsey number of $H$, denoted by $r_F(H)$, to be the minimum number of copies of $F$ in a graph which is $H$-Ramsey. This generalizes the Ramsey number and size Ramsey number of a graph. Addressing a question of Spiro, we prove that \[r_{K_3}(K_t)=\binom{r(K_t)}{3}\] for all sufficiently large $t$. We do so through a result on graph coloring: there exists an absolute constant $K$ such that every $r$-chromatic graph where every edge is contained in at least $K$ triangles must contain at least $\binom{r}{3}$ triangles in total.
academic

完全グラフの三角形ラムゼー数

基本情報

  • 論文ID: 2312.06895
  • タイトル: Triangle Ramsey numbers of complete graphs
  • 著者: Jacob Fox (Stanford), Jonathan Tidor (Princeton), Shengtong Zhang (Stanford)
  • 分類: math.CO (組合数学)
  • 発表日時: arXiv:2312.06895v2 math.CO 1 Oct 2025
  • 論文リンク: https://arxiv.org/abs/2312.06895

概要

グラフGGは、その辺の任意の二色着色が単色のHHの写しを含む場合、HH-ラムゼーと呼ばれる。グラフHHのFF-ラムゼー数rF(H)r_F(H)を、すべてのHH-ラムゼーグラフに含まれるFFの写しの最小数として定義する。これは、グラフのラムゼー数とサイズラムゼー数の概念を一般化するものである。Spiroが提起した問題に対して、著者らは十分に大きいttに対してrK3(Kt)=(r(Kt)3)r_{K_3}(K_t)=\binom{r(K_t)}{3}が成立することを証明した。証明は、グラフ着色に関する結果に基づいている：絶対定数KKが存在して、すべてのrr-色数グラフにおいて、各辺が少なくともKK個の三角形に含まれる場合、そのグラフは合計で少なくとも(r3)\binom{r}{3}個の三角形を含む。

研究背景と動機

問題の背景

  1. 古典的ラムゼー理論の拡張：従来のラムゼー理論はr(H)r(H)（任意の二色着色が単色のHHの写しを含む最小完全グラフサイズ）を研究していたが、本論文はより一般的なFF-ラムゼー数rF(H)r_F(H)（HH-ラムゼーグラフに含まれるFFの写しの最小数）を研究する。
  2. 既知の結果：ChvátalはrK2(Kt)=(r(Kt)2)r_{K_2}(K_t) = \binom{r(K_t)}{2}を証明した。すなわち、完全グラフKr(Kt)K_{r(K_t)}はすべてのKtK_t-ラムゼーグラフの中で最少の辺数を持つ。
  3. Spiroの予想：すべてのs≤ts \leq tに対して、rKs(Kt)=(r(Kt)s)r_{K_s}(K_t) = \binom{r(K_t)}{s}が成立するか？

研究の重要性

  • 理論的意義：頂点と辺以外の部分グラフFFに対するFF-ラムゼー数を研究する初めての試み
  • 方法の革新性：ラムゼー理論とグラフ着色理論の深い結合
  • 一般化の価値：Alon-Shikhermanの一般化Turán関数ex(n,F,H)ex(n,F,H)に類似

核心的貢献

  1. 主定理：十分に大きいttに対してrK3(Kt)=(r(Kt)3)r_{K_3}(K_t) = \binom{r(K_t)}{3}を証明した（定理1.3）
  2. 重要補題：グラフ着色と三角形計数の関連性を確立した（定理1.5）
  3. 技術的革新：局所稠密グラフを扱う着色技術を開発した
  4. 方法論的貢献：一般的なrKs(Kt)r_{K_s}(K_t)問題を研究するための枠組みを提供した

方法の詳細

核心戦略

証明は2つの主要なステップに分かれている：

ステップ1：ラムゼー性と着色数の関連性（命題1.4）

重要な観察：

  • GGがKtK_t-ラムゼーであれば、χ(G)≥r(Kt)\chi(G) \geq r(K_t)
  • GGがKtK_t-ラムゼー臨界であれば、GGの各辺はあるKtK_tに含まれる

証明の思路：背理法により、(r(Kt)−1)(r(K_t)-1)-着色が存在すると仮定すると、KtK_t-ラムゼーグラフの単色KtK_tを持たない二色着色を構成できる。

ステップ2：局所稠密グラフの三角形下界（定理1.5）

核心定理：絶対定数KKが存在して、すべてのrr-色数グラフにおいて、各辺が少なくともKK個の三角形に含まれる場合、そのグラフは少なくとも(r3)\binom{r}{3}個の三角形を含む。

技術的枠組み

基本的Turán論証（第2節）

定理2.2：任意のrr-色数グラフGGに対して、 t(G)+12e(G)≥(r3)+12(r2)t(G) + \frac{1}{2}e(G) \geq \binom{r}{3} + \frac{1}{2}\binom{r}{2}

証明技法：

  1. グラフ列G⊇G0⊇G0′⊇G1⊇⋯G \supseteq G_0 \supseteq G'_0 \supseteq G_1 \supseteq \cdotsを構成
  2. 各Gi′G'_iは(r−i)(r-i)-臨界部分グラフ、IiI_iはGi′G'_iの最大独立集合
  3. Turán定理を適用して各頂点の三角形数を推定

着色理論ツール（第3節）

  1. Gallaiの定理：小臨界グラフの構造
  2. Vuの定理：局所疎グラフのリスト着色数上界
  3. Harrisの定理：三角形数に基づく着色数上界
  4. 新しい補題3.5：退化局所疎グラフの着色改善

主要な証明アーキテクチャ

線形サイズグラフの処理（第4節）

補題4.1：頂点数がO(r)O(r)でクリーク数がrrに近いrr-臨界グラフの三角形数は(r3)\binom{r}{3}を超える

命題4.2：頂点数が[2r−1,Cr][2r-1, Cr]範囲内のrr-臨界グラフの三角形数は(r3)\binom{r}{3}を超える

一般的な場合の証明（第5節）

3つの場合に分けて処理：

  1. 小クリーク数の場合：Ramsey-Turán定理を利用
  2. 大クリーク数の場合：前述の線形サイズ結果を適用
  3. 統合論証：重み付き修正独立集合分解を通じて

技術的革新点

1. Turán論証の精密化

  • 古典的Turán定理の単純な適用ではなく、臨界グラフ分解により精密な界を得る
  • 「修正重み」の概念を導入して大クリークを含む場合を処理

2. 局所条件の大域化

  • 「各辺がKK個の三角形に含まれる」という局所条件から大域的三角形下界を導出
  • 確率方法と集中不等式（Azuma-Hoeffding、Talagrand不等式）を結合

3. 多スケール分析

  • 異なるサイズのグラフに異なる技術を適用：Gallaiの定理（小グラフ）、Ramsey-Turán（中等グラフ）、確率着色（大グラフ）

実験設定

本論文は純粋な理論研究であり、実験検証は含まれない。すべての結果は数学的証明により得られている。

主要な結果

核心定理

定理1.3：十分に大きいttに対して、rK3(Kt)=(r(Kt)3)r_{K_3}(K_t) = \binom{r(K_t)}{3}

支援結果

  1. 定理1.5：局所稠密グラフの三角形下界
  2. 定理2.2：改善されたTurán型不等式
  3. 補題3.5：退化グラフの着色改善

漸近結果

系2.3：rK3(Kt)≥(1−o(1))(r(Kt)3)r_{K_3}(K_t) \geq (1-o(1))\binom{r(K_t)}{3}

関連研究

古典的結果

  • Chvátalの定理：rK2(Kt)=(r(Kt)2)r_{K_2}(K_t) = \binom{r(K_t)}{2}
  • ラムゼー理論：古典的r(Kt)r(K_t)の研究
  • サイズラムゼー数：r^(H)\hat{r}(H)の関連研究

現代的発展

  • 一般化Turán問題：Alon-Shikhermanのex(n,F,H)ex(n,F,H)
  • 超グラフサイズラムゼー数：McKayらの研究
  • 確率方法：Rödl-Rucinskiの閾値関数

技術的ツール

  • グラフ着色理論：Molloy-Reedの局所疎グラフ着色
  • Ramsey-Turán理論：Erdős-Sósの定理
  • 確率集中：現代的確率不等式の応用

結論と考察

主要な結論

  1. Spiro予想がs=3s=3の場合で十分に大きいttに対して正しいことを確認した
  2. ラムゼー理論とグラフ着色理論の新しい関連性を確立した
  3. 局所稠密グラフを扱う新しい技術を開発した

制限事項

  1. 有限性の制限：「十分に大きいtt」に対してのみ成立し、小さいttの場合は未解決
  2. 特殊な場合：s=3s=3の場合のみ解決され、一般的なssは依然として開放問題
  3. 定数依存：証明に含まれる定数KKは非常に大きい可能性があり、実用的応用は限定的

今後の方向性

  1. 完全な予想：一般的なrKs(Kt)=(r(Kt)s)r_{K_s}(K_t) = \binom{r(K_t)}{s}を証明する
  2. 有限の場合：小さいtt値の場合を処理する
  3. 他のグラフペア：(F,H)(F,H)が完全グラフでない場合を研究する
  4. 計算複雑性：rF(H)r_F(H)の計算複雑性分析

深い評価

利点

  1. 理論的深さ：複数の数学分野（ラムゼー理論、グラフ着色、確率方法）を巧妙に結合
  2. 技術的革新：局所稠密条件を扱う新しい方法を開発
  3. 構造の明確性：証明は層状に進行し、論理が厳密
  4. 一般性：より広範なFF-ラムゼー数問題の研究基礎を確立

技術的ハイライト

  1. 重み付き修正技術：独立集合選択に修正重みを導入して大クリーク情報を処理
  2. 多スケール分析：異なる規模のグラフに最適な技術を適用
  3. 確率着色：確定的問題に確率方法を巧妙に適用

不足点

  1. 非構成的：証明は存在性に関するもので、具体的な極値グラフの構成は与えられていない
  2. 定数推定：関連する定数は非常に大きい可能性があり、実用的意義は限定的
  3. 技術的複雑性：証明は複数の深い結果を含み、理解の敷居が高い

影響力評価

  1. 理論的貢献：FF-ラムゼー数理論の重要な基礎を確立
  2. 方法論的価値：開発された技術的枠組みは他の組合せ問題に適用可能
  3. 後続研究：完全なSpiro予想の解決への道を開く

適用場面

  1. 理論研究：組合せ数学、極値グラフ論の研究
  2. 方法の参照：類似の局所-大域問題分析
  3. 教育的価値：現代組合せ数学の技術統合の応用を示す

参考文献

論文は23篇の重要な文献を引用しており、以下を含む：

  • 古典的ラムゼー理論（Erdősら）
  • 現代的グラフ着色理論（Alon-Krivelevich-Sudakov、Molloy-Reed）
  • 確率方法（集中不等式関連文献）
  • 一般化Turán問題（Alon-Shikhermanら）

総評：これは高品質な理論論文であり、古典的分野であるラムゼー理論において重要な進展を達成している。一般的予想の特殊な場合のみを解決しているが、開発された技術と思想は当該分野のさらなる発展に重要なツールを提供している。論文の技術的深さと革新性は顕著であり、組合せ数学分野への重要な貢献である。