禁止半導出部分構造を持つグラフにおける大クリーク

基本情報

• 論文ID: 2511.13073
• タイトル: Large cliques in graphs with forbidden semi-induced structures
• 著者: Nannan Chen (山東大学 & IBS)、Yulai Ma (南開大学)、Fan Yang (山東大学 & IBS)
• 分類: math.CO (組合論)
• 提出日時: 2025年11月17日
• 論文リンク: https://arxiv.org/abs/2511.13073

要約

本論文は、禁止半導出部分構造を持つグラフにおける大クリークの存在性問題を研究している。Holmsenは2022年に、少なくとも $c\binom{n}{r}$ 個の $r$-クリークを含むが、導出完全 $r$-部グラフ $K_{2,\ldots,2}$ を含まないグラフは、必ず $Ω(c^{2^{r-1}}n)$ の位数を持つクリークを含むことを証明した。本論文は、$K_{2,\ldots,2}$ に関連する半導出部分構造を禁止することにより、少なくとも $c\binom{n}{r}$ 個の $K_r$ コピーを含む $n$ 頂点グラフ $G$ は、必ず $Ω(cn)$ の位数を持つクリークを含むことを証明している。この結果は、Holmsen界における $c$ への依存性を $c^{2^{r-1}}$ から $c$ に関する線形に改善し、有界数の構造のみを禁止する必要がある。さらに、この方法はVC次元の概念と自然に関連している。

研究背景と動機

問題背景

1. 古典的Turán理論: Turan定理およびその推広（Erdős-Stone-Simonovits定理）は、禁止非導出部分グラフの極値問題を研究している。色数 $χ(H) ≥ 3$ のグラフ $H$ に対して、$H$ を部分グラフとして禁止すると、極値グラフは漸近的に $(χ(H)-1)$-部グラフとなり、クリーク数は定数で界限される。
2. 導出部分グラフの場合: 導出部分グラフを禁止する場合、状況は全く異なる。Gyárfás、Hubenko、Solymosi (2002)は、$n$ 頂点グラフ $G$ が少なくとも $c\binom{n}{2}$ 本の辺を持ち、導出 $K_{2,2}$ を含まない場合、$ω(G) ≥ \frac{c^2}{10}n$ であることを証明した。
3. 弦グラフの厳密界: 弦グラフ（長さ4以上の導出サイクルを禁止）はより優れた界を達成している：$ω(G) ≥ (1-\sqrt{1-c})n$。$c$ が小さい場合、これは $Ω(cn)$ である。
4. Holmsenの推広: Holmsen (2020)は $K_{2,2}$ の場合を多部版に推広し、導出 $K_r[2]$（$K_r$ の2-膨張）を禁止するグラフは $Ω(c^{2^{r-1}}n)$ の位数を持つクリークを含むことを証明した。

研究動機

Holmsenの結果は $n$ に関して線形であるが、$c$ への界は $r$ の増加に伴い急速に悪化する。本論文の中心的な問題は：定理1.1から定理1.2への改善と同様に、より多くの（ただし有界数の）構造を禁止することにより、Holmsen界を改善できるか？

重要性

• この問題は極値グラフ理論と抽象Helly定理を結びつける
• 導出部分グラフ禁止条件とクリーク数の関係を理解する上で基礎的意義を持つ
• グラフ構造におけるVC次元の役割を明らかにする

主要な貢献

1. 主定理: 少なくとも $c\binom{n}{r}$ 個の $K_r$ コピーを含む導出 $K_r^{[2]}$-自由グラフ $G$ に対して、$ω(G) ≥ \frac{c}{18r}n$ であることを証明した（定理1.5）
2. 界の改善: Holmsenの $Ω(c^{2^{r-1}}n)$ 界を $Ω(cn)$ に改善し、$c$ に関する線形依存性を実現した
3. 有界禁止構造: 最大 $2^{\binom{r}{2}}$ 個の導出部分構造のみを禁止する必要がある（弦グラフの無限個と比較して）
4. VC次元方法: 半導出部分グラフとVC次元の自然な関連性を確立し、既存の双導出部分グラフ理論を推広した
5. 構造的洞察: 弦グラフより遥かに少ない構造を禁止しても、線形サイズのクリークを保証できることを明らかにした

方法の詳細

タスク定義

入力: $n$ 頂点グラフ $G$。以下を満たす：

• 少なくとも $c\binom{n}{r}$ 個の $K_r$ コピーを含む（$c > 0$ は定数）
• 導出 $K_r^{[2]}$-自由（$K_r^{[2]}$ 内のいかなるグラフも導出部分グラフとして含まない）

出力: $G$ が少なくとも $\frac{c}{18r}n$ の位数を持つクリークを含むことを証明する

主要定義:

• $K_r[2]$: $K_r$ の2-膨張。各頂点をサイズ2の独立集合で置換
• $K_r^{[2]}$: $K_r[2]$ の部分グラフ族。辺集合の形式は $(E(K_r[2])\backslash E(K_{U'})) \cup E'$。ここで $U' = \{u'_1, \ldots, u'_r\}$ は各部分の第2頂点集合、$E' \subseteq E(K_{U'})$

中核的アーキテクチャ

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

1. VC次元界（主張2.3）

中核補題: 導出 $K_r^{[2]}$-自由グラフの極大クリーク集合 $MC(G)$ のVC次元は最大 $r-1$ である。

証明の概要:

• サイズ $r$ の集合 $S = \{u_1, \ldots, u_r\}$ が $MC(G)$ により粉砕されると仮定
• 各 $i \in [r]$ に対して、$K_i \cap S = S \backslash \{u_i\}$ を満たす極大クリーク $K_i$ が存在
• 極大性により、$u_i u'_i \notin E(G)$ を満たす $u'_i \in K_i \backslash S$ が存在
• すると $\{u_1, u'_1, \ldots, u_r, u'_r\}$ は $K_r^{[2]}$ 内のあるグラフを導出し、矛盾

2. Sauer-Shelah補題の応用

VC次元 $k$ の集合系 $\mathcal{F}$ に対して、任意のサイズ $m$ の集合 $S$ は以下を満たす： $|\mathcal{F}|_S| \leq \sum_{i=0}^{k} \binom{m}{i}$

本論文の場合、$k = r-1$、$m = \lfloor\frac{9r}{c}\rfloor$ を選択すると： $|MC(G)|_{S_m}| \leq \sum_{i=0}^{r-1} \binom{m}{i} < \frac{1}{4}c\binom{m}{r}$

3. 確率論証

背理法: $ω(G) < c'n$ と仮定。ここで $c' = \frac{c}{18r}$

ランダム選択: $V(G)$ から $S_r \subseteq S_m$ をランダムに選択。$|S_r| = r$、$|S_m| = m$

確率分析:

• $S_r$ が導出クリークである確率は少なくとも $c$
• $S_r$ が導出クリークであり、サイズ $< c'n$ の極大クリーク $K$ に含まれる場合、$S_m$ が $S_r$ を含むが $S_m \backslash S_r$ が $K$ 内のいかなる頂点も含まない確率は少なくとも： $\frac{\binom{n-c'n}{m-r}}{\binom{n-r}{m-r}} \geq \left(\frac{n-c'n-m}{n-m}\right)^m \geq e^{-2c'm} \geq \frac{1}{4}$
• したがって、$S_r = S_m \cap K$ である確率は少なくとも $\frac{1}{4}c$
• 条件を満たす $S_r$ の期待数は少なくとも $\frac{1}{4}c\binom{m}{r}$

矛盾: これはSauer-Shelah補題により与えられた上界と矛盾する。

技術的革新点

1. 半導出構造の導入: $K_r^{[2]}$ 族は構造制限の強度と数量を巧妙に均衡させ、十分な制約力を保証しながら禁止構造の数を有界に保つ
2. VC次元の自然な関連性: 極大クリーク系のVC次元をグラフの導出部分構造と直接関連付け、新しい分析視点を提供
3. 精密な確率推定: ランダム選択フレームワークの下で、慎重な確率計算によりクリーク密度とクリークサイズの定量的関係を確立
4. パラメータ最適化: $m = \lfloor\frac{9r}{c}\rfloor$ を選択することで、Sauer-Shelah界と確率下界がちょうど矛盾を生じさせる

実験設定

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

理論的検証

• 極値例: $r=2$ の場合、論文は導出 $K_2^{[2]}$-自由グラフ（導出 $P_4$ と $K_{2,2}$ を禁止）が弦グラフの部分クラスを形成することを指摘
• 厳密性分析: 精確な極値構成は与えられていないが、界の位数は合理的であることが証明されている

実験結果

主要な理論結果

定理1.5（主結果）: $r ≥ 2$、$0 < c < 1$ とし、$G$ は少なくとも $c\binom{n}{r}$ 個の $K_r$ コピーを含む $n$ 頂点グラフとする。$G$ が導出 $K_r^{[2]}$-自由であれば、充分大きい $n$ に対して、 $ω(G) ≥ \frac{c}{18r}n$

既存結果との比較

主要な改善

1. 指数から線形へ: $c$ への依存性を $c^{2^{r-1}}$ から $c/r$ に改善
   • $r=3$ の場合、$c^4$ から $c/3$ に改善
   • $r=5$ の場合、$c^{16}$ から $c/5$ に改善
2. 有界構造数: $2^{\binom{r}{2}}$ 個の構造のみを禁止
   • $r=2$: 2個の構造
   • $r=3$: 8個の構造
   • $r=4$: 64個の構造
3. 最適性: $r=2$ の場合、本論文の結果は弦グラフ界と位数において一致（両方とも $Ω(cn)$）であるが、禁止構造がより少ない

関連研究

古典的極値グラフ理論

1. Turan定理 (1941): $ex(n, K_k)$ の精確な値と極値グラフを決定
2. Erdős-Stone-Simonovits定理 (1946, 1966): $ex(n,H) = \left(1 - \frac{1}{χ(H)-1}\right)\binom{n}{2} + o(n^2)$
   • 非二部グラフ $H$ に対して、漸近挙動を完全に解決
   • 二部グラフに対しては、$ex(n,H) = o(n^2)$ のみを与える

導出部分グラフの極値理論

3. Gyárfás-Hubenko-Solymosi (2002):
   • 導出 $K_{2,2}$-自由グラフ：$ω(G) ≥ \frac{c^2}{10}n$
   • $C_4$-自由グラフ（弦グラフ）：$ω(G) ≥ (1-\sqrt{1-c})n$
4. Abbott-Katchalski (1979): 弦グラフの厳密界を独立に証明
5. Loh et al. (2018): 導出 $K_{2,t}$-自由グラフへの推広
6. Holmsen (2020):
   • 超グラフと多部版への推広
   • 抽象colorful Hellyが抽象fractional Hellyを蕴含することを証明
   • 本論文はHolmsenのグラフ理論結果を直接改善

グラフ理論におけるVC次元の応用

7. Nguyen-Scott-Seymour (2025): 双導出部分グラフ密度とVC次元の関連性を確立
8. Sauer (1972), Shelah (1972): VC次元の基本界を独立に証明（Sauer-Shelah補題）

本論文の位置付け

本論文はHolmsenの研究に基づき、半導出部分構造とVC次元方法を導入することにより、定量的改善を実現している。弦グラフ理論との関連性は $r=2$ の場合に自然な説明を提供する。

結論と議論

主要な結論

1. 定量的改善: $K_r^{[2]}$ 族を禁止することにより（最大 $2^{\binom{r}{2}}$ 個の構造）、クリーク数下界を $Ω(c^{2^{r-1}}n)$ から $Ω(cn)$ に改善
2. 方法論的貢献: 半導出部分グラフとVC次元の自然な関連性を確立し、既存の理論フレームワークを推広
3. 構造的洞察: 有限の構造禁止条件が線形サイズのクリークを保証するのに十分であることを明らかにし、弦グラフのように無限個の構造を禁止する必要がないことを示した

限界

1. 定数因子: 界の定数 $\frac{1}{18r}$ は最適でない可能性があり、論文は厳密性を議論していない
2. 禁止構造数: 有界ではあるが、$2^{\binom{r}{2}}$ は $r$ に関して指数的に増加し、$r$ が大きい場合は依然として多い
3. 極値構成の欠落: 論文は下界を達成する極値グラフの構成を提供していない
4. 漸近性: 結果は $n$ が充分大きいことを要求し、具体的な閾値は明確にされていない

今後の方向

論文の結論部分では、開放問題を明確に提示している：

中核的問題: $c^{2^{r-1}}$ から $c$ への線形依存性への転換はいつ発生するか？より正確には、$c$ に関する線形界を強制するのに必要な最小禁止構造数はいくつか？

可能な研究方向：

1. 線形界を達成する最小禁止構造族の決定
2. 定数因子 $\frac{1}{18r}$ の改善
3. 極値例の構成または界の厳密性の証明
4. 超グラフへの推広
5. 他の半導出構造の禁止条件の探索

深い評価

利点

1. 重要な定量的改善:
   • 指数依存から線形への改善は実質的進展
   • 応用（抽象Helly定理など）に重要な意義を持つ
2. 優雅な証明技法:
   • VC次元方法は統一的分析フレームワークを提供
   • 確率論証は簡潔で有力
   • 証明は完全に自己完結し、基本的ツールのみに依存
3. 概念的革新:
   • $K_r^{[2]}$ 族の定義は制約強度と数量を巧妙に均衡
   • 半導出構造の導入は自然な推広
4. 明確な記述:
   • 動機の説明は十分
   • 技術的詳細は完全
   • 既存研究との関係は明確
5. 理論的深さ:
   • 導出部分グラフ理論の深層構造を明らかに
   • 複数の数学分野を結びつける（極値グラフ理論、VC次元理論、組合幾何）

不足

1. 定数最適化:
   • $\frac{1}{18r}$ の定数は十分に精密でない可能性
   • 界の厳密性または一致する上界構成について議論なし
2. 構造数への依存:
   • $2^{\binom{r}{2}}$ は依然として $r$ に関して急速に増加
   • より少ない禁止構造で類似結果を達成できるかについて未探索
3. 具体的閾値の欠落:
   • 「充分大きい $n$」は定量化されていない
   • 実際の応用に影響する可能性
4. 推広性の議論不足:
   • 方法が他の禁止構造に適用可能かについて未議論
   • 超グラフ情形との関連は序論でのみ言及
5. 開放問題の具体性:
   • 重要な問題を提示しているが、予想や部分結果は与えられていない

影響力評価

理論的影響:

• 導出部分グラフ極値理論に新しいツールを提供
• VC次元方法はさらなる応用を刺激する可能性
• 抽象Helly定理研究に直接的貢献

実用的価値:

• 主に理論的性質
• アルゴリズム的グラフ理論と計算幾何で応用の可能性

再現性:

• 証明は完全に検証可能
• 計算実験を含まない

潜在的引用価値:

• 極値組合論分野で高い引用が予想される
• 該当分野の標準参考文献となる可能性

適用場面

1. 理論研究:
   • 極値グラフ理論における禁止導出部分グラフ問題
   • 組合構造におけるVC次元の応用
   • 抽象Helly定理とその推広
2. 関連問題:
   • 他の半導出構造の研究
   • クリーク数と他のグラフパラメータの関係
   • ランダムグラフにおけるクリーク構造
3. 潜在的応用:
   • アルゴリズム設計（構造的性質の利用）
   • 計算複雑性理論
   • 組合最適化問題

参考文献

論文は以下の主要文献を引用している：

1. Abbott & Katchalski (1979): 区間グラフのTuran型問題
2. Erdős & Simonovits (1966), Erdős & Stone (1946): ESS定理
3. Gyárfás, Hubenko & Solymosi (2002): $C_4$-自由グラフにおける大クリーク
4. Holmsen (2020): 超グラフにおける禁止部分構造の大クリーク（本論文が直接改善する研究）
5. Loh et al. (2018): 導出Turan数
6. Nguyen, Scott & Seymour (2025): 導出部分グラフ密度とVC次元
7. Sauer (1972), Shelah (1972): VC次元の基本界
8. Turán (1941): 古典的Turan定理

総合評価: これは組合数学における高品質な論文であり、極値グラフ理論の重要な問題で実質的進展を達成している。半導出部分構造とVC次元方法を導入することにより、著者はHolmsenの指数界を線形界に成功裏に改善し、同時に禁止構造数の有界性を保持している。証明技法は優雅で洞察に富み、該当分野に新しい研究ツールと方向を提供する。論文の主要な貢献は理論レベルであるが、その方法と思想は関連分野に広範な影響を与える可能性がある。