極値グラフ理論

極値グラフ理論は、それ自体が数学の一分野である組合せ論の一分野であり、極値組合せ論とグラフ理論の交差点に位置します。本質的に、極値グラフ理論は、グラフのグローバルな特性がローカルなサブ構造にどのように影響するかを研究します。 ^[1] 極値グラフ理論の結果は、グローバル（頂点や辺の数など）とローカル（特定のサブグラフの存在など）の両方のさまざまなグラフ特性間の定量的な関係を扱い、極値グラフ理論の問題は、多くの場合、最適化問題として定式化できます。つまり、グラフが満たさなければならないいくつかの制約が与えられた場合、グラフのパラメータはどれだけ大きくまたは小さくできるかということです。 ^[2] このような最適化問題の最適解であるグラフは極値グラフと呼ばれ、極値グラフは極値グラフ理論における重要な研究対象です。

極値グラフ理論は、ラムゼー理論、スペクトルグラフ理論、計算複雑性理論、加法組合せ論などの分野と密接に関連しており、確率的手法を頻繁に採用しています。

マンテルの定理（1907年）とトゥランの定理（1941年）は、極値グラフ理論の研究における最初のマイルストーンのいくつかでした。 ^{[4]特に、トゥランの定理は、後に}エルデシュ-ストーン定理（1946年） などの結果を見つける動機となりました。^[1]この結果は、彩色数と-freeグラフの最大辺数を結び付けているため、驚くべきものです。エルデシュ-ストーンの別の証明は1975年に与えられ、極値グラフ理論の問題の解決に不可欠なテクニックであるセメレディ正則補題を利用しました。 ^[4]${\displaystyle H}$

グラフの適切な（頂点）彩色とは、2つの隣接する頂点が同じ色を持たないようにグラフの頂点を彩色することです。適切に彩色するために必要な最小の色数はの彩色数と呼ばれ、 と表記されます。特定のグラフの彩色数を決定することは、極限グラフ理論における基本的な問題です。なぜなら、この分野および関連分野の多くの問題がグラフ彩色の観点から定式化できるからです。^[2]${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle \chi (G)}$

グラフの彩色数の 2 つの単純な下限は、クリーク数(クリークのすべての頂点は異なる色を持つ必要がある)と によって与えられます。ここで は独立数です。特定の色を持つ頂点の集合は、独立した集合を形成する必要があるためです。 ${\displaystyle G}$ ${\displaystyle \omega (G)}$${\displaystyle |V(G)|/\alpha (G)}$${\displaystyle \alpha (G)}$

貪欲な彩色により上限 が得られ、ここで はの最大次数です。 が奇数サイクルでもクリークでもない場合、ブルックスの定理によれば上限は に減らすことができます。 が平面グラフの場合、4 色定理によれば の彩色数は最大で 4 です。 ${\displaystyle \chi (G)\leq \Delta (G)+1}$${\displaystyle \デルタ (G)}$${\displaystyle G}$${\displaystyle G}$${\displaystyle \デルタ (G)}$${\displaystyle G}$${\displaystyle G}$

一般に、与えられたグラフが規定の数の色で着色されているかどうかを判断することはNP 困難であることが知られています。

頂点彩色に加えて、辺彩色などの他のタイプの彩色も研究されています。グラフの彩色指数は 、グラフの適切な辺彩色における色の最小数であり、ビイジングの定理によれば、グラフの彩色指数はまたは のいずれかです。 ${\displaystyle \chi '(G)}$${\displaystyle G}$${\displaystyle G}$${\displaystyle \デルタ (G)}$${\displaystyle \Delta (G)+1}$

禁制部分グラフ問題は、極値グラフ理論における中心的な問題の 1 つです。禁制部分グラフ問題は、グラフ が与えられたときに、と同型の部分グラフを含まない -頂点グラフの辺の最大数を求める問題です。 ${\displaystyle G}$${\displaystyle \operatorname {ex} (n,G)}$${\displaystyle n}$${\displaystyle G}$

が完全グラフの場合、トゥランの定理はの正確な値を与え、この最大値に達するすべてのグラフを特徴付けます。このようなグラフはトゥラングラフと呼ばれます。非二部グラフの場合、エルデシュ-ストーン定理はの彩色数に関して の漸近値を与えます。が二部グラフの場合の の漸近値を決定する問題は未解決です。が完全二部グラフの場合、これはザランキエヴィチ問題として知られています。 ${\displaystyle G=K_{r}}$${\displaystyle \operatorname {ex} (n,K_{r})}$${\displaystyle G}$${\displaystyle \operatorname {ex} (n,G)}$${\displaystyle G}$${\displaystyle \operatorname {ex} (n,G)}$${\displaystyle G}$${\displaystyle G}$

グラフ内のグラフの準同型性密度は 、の頂点集合から の頂点集合へのランダムに選択された写像もグラフ準同型である確率を表します。 これは、グラフが のサブグラフとして見つかる頻度を表すサブグラフ密度と密接に関連しています。 ${\displaystyle t(H,G)}$${\displaystyle H}$${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$

禁制部分グラフ問題は、-密度がゼロであるグラフの辺密度を最大化する問題として言い換えることができ、これは自然にグラフ準同型不等式の形で一般化され、さまざまなグラフに関連する不等式になります。準同型密度を密なグラフの極限として生じるオブジェクトであるグラフオンに拡張することにより、グラフ準同型密度を積分の形で記述でき、コーシー・シュワルツの不等式やヘルダーの不等式などの不等式を使用して準同型不等式を導出できます。 ${\displaystyle G}$${\displaystyle t(H,G)}$${\displaystyle H}$

準同型密度に関する主要な未解決問題は、シドレンコの予想であり、これは、グラフの辺密度に関して、2部グラフの準同型密度の厳密な下限を述べている。 ${\displaystyle G}$${\displaystyle G}$

セメレディの正則性補題は、すべてのグラフが次の意味で「正則」であることを述べています。任意のグラフの頂点集合は、ほとんどの部分ペア間の二部グラフがランダム二部グラフのように動作するように、限られた数の部分に分割できます。 [ ^2] この分割は元のグラフの構造的な近似を与え、元のグラフの特性に関する情報を明らかにします。

正則性補題は極限グラフ理論における中心的な結果であり、加法組合せ論や計算複雑性理論といった隣接分野にも数多くの応用がある。(セメレディ)正則性に加えて、強い正則性やフリーズ・カンナンの弱い正則性などグラフ正則性の密接に関連する概念も研究されており、またハイパーグラフへの正則性の拡張も研究されている。

グラフの正則性の応用では、多くの場合、計数補題と除去補題の形式が利用されます。最も単純な形式では、グラフの計数補題は、正規のパーティション内の部分のペア間の正則性を使用してサブグラフの数を概算し、グラフの除去補題は、特定のサブグラフのコピーが少数のグラフが与えられた場合、少数のエッジを削除してサブグラフのすべてのコピーを削除できることを示します。

関連分野

• ラムゼー理論
• ラムゼー・トゥラン理論
• スペクトルグラフ理論
• 加法的な組み合わせ論
• 計算複雑性理論
• 確率的組合せ論

技術と方法

• 確率的方法
• 従属ランダム選択
• コンテナ方式
• ハイパーグラフ正則性法

定理と推測（上記に加えて）

• オーレの定理
• ルザ・セメレディ問題