極値グラフ理論

極値グラフ理論は、特定のサブストラクチャを回避しながら、グラフがどれほど大きくまたは密になり得るかを問い、その極値的な構成を特定する。

Definition

固定されたサブグラフの欠如などの構造的制約の下で、辺の数などのグラフパラメータの最大値または最小値の研究。

Scope

このトピックは、Turan型の問題、すなわち与えられたサブグラフを持たないグラフにおける最大辺数に焦点を当てており、Mantelの定理とTuranの定理から始まり、任意の禁止サブグラフに対する漸近的な極値密度を決定するErdos-Stoneの定理へと拡張される。密度、構造、およびSzemerediの正則性手法の相互作用を紹介する。

Core questions

• 与えられたサブグラフのコピーを含まないn個の頂点を持つグラフにおける最大辺数はいくつか？
• これらの極値的な上限を達成するグラフはどれか？
• 禁止サブグラフの彩色数は、漸近的な答えをどのように支配するか？
• 正則性手法は、密なグラフをどのようにして有界な構造に還元するのか？

Key concepts

• 禁止サブグラフ
• Turanグラフ
• Mantelの定理
• 極値数（Turan数）
• Erdos-Stoneの定理
• Szemerediの正則性補題

Key theories

Turanの定理

r+1個の頂点を持つ完全サブグラフを持たないn個の頂点を持つすべてのグラフの中で、バランスの取れた完全r部グラフが最も多くの辺を持ち、Mantelの三角形を含まないグラフの辺数の上限を一般化し、極値グラフ理論の基礎となっている。

Erdos-Stoneの定理

任意の固定された禁止サブグラフHに対して、Hを含まないグラフの最大辺密度は、Hの彩色数によって漸近的に決定され、Turan型の極値結果を統一する。

Clinical relevance

極値密度結果は、大規模ネットワークおよび制約システムの構造を制限し、この分野で開発された正則性手法は、特性テスト、理論計算機科学、および加法的組み合わせ論に応用されている。

History

Mantelの1907年の三角形を含まないグラフの辺数の上限と、Turanの1941年の一般化がこの分野を立ち上げた。Erdos-Stone-Simonovitsの理論とSzemerediの正則性補題は、これを現代組み合わせ論の中心的な柱とした。

Key figures

• Paul Turan
• Paul Erdos
• Endre Szemeredi

Seminal works

• bollobas1998
• diestel2017

Frequently asked questions

Turan型の問題とは何か？

これは、固定されたサブグラフを回避しながらグラフが持ち得る最大の辺数を問うものであり、典型的な例は、三角形を含まないグラフにおける最大辺数である。

極値グラフ理論はRamsey理論とどのように関連しているか？

どちらも避けられない構造を研究するが、極値理論は禁止サブグラフを固定し辺数を最大化するのに対し、Ramsey理論はグラフが十分に大きくなると単色構造を保証する。