トゥランの定理

これはトゥランのオリジナルの証明です。${\displaystyle K_{r+1}}$-無料グラフ${\displaystyle n}$辺の数が最大となる頂点を見つけます。${\displaystyle K_{r}}$（最大性によって存在する）頂点を集合に分割する${\displaystyle A}$の${\displaystyle r}$頂点${\displaystyle K_{r}}$そしてセット${\displaystyle B}$の${\displaystyle nr}$他の頂点。

さて、上記の辺は次のように境界付けできます。

• 正確には${\displaystyle {\binom {r}{2}}}$エッジ内${\displaystyle A}$。
• 最大で${\displaystyle (r-1)|B|=(r-1)(nr)}$エッジ間の${\displaystyle A}$そして${\displaystyle B}$頂点がないため${\displaystyle B}$すべての${\displaystyle A}$。
• エッジの数${\displaystyle B}$は最大でエッジの数です${\displaystyle T(nr,r)}$帰納的仮説による。

これらの境界を追加すると、結果が得られます。^{[ 1 ] [ 3 ]}

この証明はポール・エルデシュによるものです。頂点${\displaystyle v}$最大次数。集合を考える。${\displaystyle A}$隣接していない頂点${\displaystyle v}$そしてセット${\displaystyle B}$に隣接する頂点${\displaystyle v}$。

次に、すべてのエッジを削除します。${\displaystyle A}$そしてすべてのエッジを描画します${\displaystyle A}$そして${\displaystyle B}$これにより、最大性仮定によりエッジの数が増加し、グラフは維持されます。${\displaystyle K_{r+1}}$-無料。さて、${\displaystyle B}$は${\displaystyle K_{r}}$-無料なので、同じ議論を繰り返すことができます${\displaystyle B}$。

この議論を繰り返すと、最終的にはトゥラングラフと同じ形式のグラフが得られます。トゥラングラフは独立集合の集合であり、異なる独立集合に属する2つの頂点間にエッジがあります。簡単な計算により、このグラフのエッジの数は、すべての独立集合のサイズが可能な限り等しい場合に最大になることがわかります。^{[ 3 ] [ 4 ]}

この証明は、ジコフの対称化証明と同様に、グラフが完全多部グラフである場合に還元し、エッジの数が最大になるのは、${\displaystyle r}$できるだけサイズが等しい独立集合を作成する。この手順は次のように実行できる。

させて${\displaystyle S_{1},S_{2},\ldots ,S_{r}}$多部グラフの独立集合を とする。2 つの頂点間に辺が存在するのは、それらが同じ独立集合に属さない場合のみであるため、辺の数は

$${\displaystyle \sum _{i\neq j}\left|S_{i}\right|\left|S_{j}\right|={\frac {1}{2}}\left(n^{2}-\sum _{i}\left|S_{i}\right|^{2}\right),}$$

ここで、左辺は直接計数から導かれ、右辺は補数計数から導かれる。${\displaystyle \left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}}$境界は、コーシー・シュワルツの不等式を適用して、${\textstyle \sum \limits _{i}\left|S_{i}\right|^{2}}$右辺の項で十分です。${\textstyle \sum \limits _{i}\left|S_{i}\right|=n}$。

Turánグラフが最適であることを証明するには、2つのグラフが最適である必要はないと主張できます。${\displaystyle S_{i}}$大きさが1つ以上異なる。特に、$\displaystyle \left|S_{i}\right|\geq \left|S_{j}\right|+2}$一部の人にとって${\displaystyle i\neq j}$1つの頂点を移動${\displaystyle S_{i}}$に${\displaystyle S_{j}}$（そしてそれに応じて辺を調整する）ことで、合計値は増加する。これは、上記の辺の数の式の両辺の変化を調べるか、移動した頂点の次数が増加することに気づけば分かる。

この証明はモツキンとストラウス（1965）によるものである。彼らはまず、${\displaystyle K_{r+1}}$頂点にラベルが付いたフリーグラフ${\displaystyle 1,2,\ldots ,n}$関数を最大化することを考慮する$${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})=\sum _{i,j\ {\text{adjacent}}}x_{i}x_{j}}$$全体的に非負${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$合計付き${\displaystyle 1}$この関数は、グラフとその辺のラグランジアンとして知られています。

彼らの証明の背後にある考え方は、もし${\displaystyle x_{i},x_{j}}$両方ともゼロではないが${\displaystyle i,j}$グラフ上で隣接していない関数$${\displaystyle f(x_{1},\ldots ,x_{i}-t,\ldots ,x_{j}+t,\ldots ,x_{n})}$$線形${\displaystyle t}$したがって、置き換えることができます${\displaystyle (x_{i},x_{j})}$どちらか${\displaystyle (x_{i}+x_{j},0)}$または${\displaystyle (0,x_{i}+x_{j})}$関数の値を減少させることなく。したがって、最大で${\displaystyle r}$関数が最大化される非ゼロ変数。

さて、コーシー・シュワルツの不等式によれば、最大値は最大で $\displaystyle {\frac {1}{2}}\left(1-{\frac {1}{r}}\right)}$プラグを差し込む${\displaystyle x_{i}={\frac {1}{n}}}$すべての人々のために${\displaystyle i}$最大値は少なくとも${\displaystyle {\frac {|E|}{n^{2}}}}$所望の境界を与える。^{[ 3 ] [ 5 ]}

この証明の重要な主張は、カロとウェイによって独立に発見された。この証明は、ノガ・アロンとジョエル・スペンサーの著書『確率的方法』によるものである。この証明は、次数を持つすべてのグラフが${\displaystyle d_{1},d_{2},\ldots ,d_{n}}$少なくともサイズの独立したセットを持つ$${\displaystyle S={\frac {1}{d_{1}+1}}+{\frac {1}{d_{2}+1}}+\cdots +{\frac {1}{d_{n}+1}}.}$$証明では、次のような独立集合を見つけようと試みます。

• 頂点のランダムな順列を考えてみましょう。${\displaystyle K_{r+1}}$-フリーグラフ
• 前のどの頂点にも隣接していない頂点をすべて選択します。

次数 の頂点${\displaystyle d}$確率でこれに含まれる${\displaystyle {\frac {1}{d+1}}}$したがって、このプロセスでは平均${\displaystyle S}$選択された集合内の頂点。

この事実を補グラフに適用し、コーシー・シュワルツの不等式を用いて選択された集合のサイズを制限することで、トゥランの定理が証明される。^{[ 3 ]}詳しくは、条件付き確率の方法§ トゥランの定理を参照のこと。

アイグナーとジーグラーは、5つの証明のうち最後のものを「最も美しいもの」と呼んでいる。その起源は不明だが、この手法は、ジコフがトゥランの定理の一般化の証明^{[ 6 ]}で使用したことから、ジコフ対称化と呼ばれることが多い。この証明は、${\displaystyle K_{r+1}}$-フリーグラフであり、エッジ数を増やしながら、それをトゥラングラフにより近づけるための手順を適用します。

特に、${\displaystyle K_{r+1}}$-フリーグラフの場合、以下の手順が適用されます。

• もし${\displaystyle u,v}$隣接していない頂点であり、${\displaystyle u}$より高い度数を持つ${\displaystyle v}$、 交換する${\displaystyle v}$コピー付き${\displaystyle u}$隣接していないすべての頂点の次数が同じになるまで、これを繰り返します。
• もし${\displaystyle u,v,w}$頂点は${\displaystyle u,v}$そして${\displaystyle v,w}$隣接していないが${\displaystyle u,w}$隣接して、両方を置き換える${\displaystyle u}$そして${\displaystyle w}$コピー付き${\displaystyle v}$。

これらの手順はすべてグラフを維持します${\displaystyle K_{r+1}}$エッジ数を増やしながら、自由度を高める。

さて、非隣接関係は同値関係を形成します。同値類により、任意の極大グラフはトゥラングラフと同じ形式になります。最大次数頂点の証明と同様に、簡単な計算により、すべての独立集合のサイズが可能な限り等しいときにエッジの数が最大になることがわかります。^{[ 3 ]}

トゥランの定理は、${\displaystyle K_{r+1}}$-フリーグラフは${\displaystyle \left(1-{\frac {1}{r}}+o(1)\right){\frac {n^{2}}{2}}}$エルデシュ・ストーンの定理は、${\displaystyle o(n^{2})}$他のすべてのグラフにエラーがあります。

（エルデシュ＝ストーン）${\displaystyle H}$彩色数を持つグラフ${\displaystyle \chi (H)}$グラフ内のエッジの最大数は、${\displaystyle H}$サブグラフとして表示されません$${\displaystyle \left(1-{\frac {1}{\chi (H)-1}}+o(1)\right){\frac {n^{2}}{2}}}$$どこで${\displaystyle o(1)}$定数は${\displaystyle H}$。

Turán グラフを見ると、${\displaystyle T(n,\chi (H)-1)}$コピーを含めることはできません${\displaystyle H}$したがって、トゥラングラフは下限を確立します。${\displaystyle K_{r+1}}$色数を持つ${\displaystyle r+1}$、トゥランの定理は、${\displaystyle H}$は${\displaystyle K_{r+1}}$。

グラフにコピーなしでいくつのエッジを含めることができるかという一般的な質問${\displaystyle H}$これは禁止部分グラフ問題です。

トゥランの定理のもう一つの自然な拡張は、次の質問です。グラフに${\displaystyle K_{r+1}}$s、何部${\displaystyle K_{a}}$それは可能でしょうか？トゥランの定理は、${\displaystyle a=2}$ジコフの定理はこの疑問に答える。

（ジコフの定理）グラフは${\displaystyle n}$頂点がない${\displaystyle K_{r+1}}$s と可能な限り最大の数${\displaystyle K_{a}}$sはトゥラングラフである${\displaystyle T(n,r)}$

これは、Zykov (1949) が Zykov 対称化^{[ 1 ] [ 3 ]}を使用して初めて示しました。Turán グラフには${\displaystyle r}$サイズが約${\displaystyle {\frac {n}{r}}}$、その数${\displaystyle K_{a}}$s in${\displaystyle T(n,r)}$あたり${\displaystyle {\binom {r}{a}}\left({\frac {n}{r}}\right)^{a}}$2016年のアロンとシケルマンの論文では、トゥランの定理のエルデシュ・ストーンによる一般化に似た、以下の一般化が示されている。

（アロン＝シケルマン、2016年）${\displaystyle H}$彩色数を持つグラフである${\displaystyle \chi (H)>a}$可能な限り最大の数${\displaystyle K_{a}}$コピーのないグラフ内のs${\displaystyle H}$は ${\displaystyle (1+o(1)){\binom {\chi (H)-1}{a}}\left({\frac {n}{\chi (H)-1}}\right)^{a}.}$^{[ 9 ]}

エルデシュ・ストーンのトゥラングラフと同様${\displaystyle T(n,\chi (H)-1)}$望ましい数のコピーを取得する${\displaystyle K_{a}}$。

トゥランの定理は、グラフの辺準同型密度が厳密に上回っている場合、${\displaystyle 1-{\frac {1}{r-1}}}$ゼロでない数${\displaystyle K_{r}}$s. より一般的な質問をすることもできます。グラフのエッジ密度が与えられた場合、密度について何が言えるでしょうか。${\displaystyle K_{r}}$s?

この問いに答える上で問題となるのは、与えられた密度に対して、どのグラフでも到達できないものの、無限列のグラフによって近づくことができる境界が存在する可能性がある点です。この問題を解決するために、重み付きグラフやグラフオンがしばしば検討されます。特に、グラフオンは任意の無限列のグラフの極限を含みます。

特定のエッジ密度の場合${\displaystyle d}$最大の建設${\displaystyle K_{r}}$密度は以下のとおりです。

頂点の数を取る${\displaystyle N}$無限大に近づく。${\displaystyle {\sqrt {d}}N}$頂点の集合を探索し、2つの頂点が選択された集合に含まれている場合に限り、それらを接続する。

これにより${\displaystyle K_{r}}$密度${\displaystyle d^{k/2}.}$最小の建設${\displaystyle K_{r}}$密度は以下のとおりです。

頂点の数を無限大に近づける。${\displaystyle t}$整数とする。${\displaystyle 1-{\frac {1}{t-1}}<d\leq 1-{\frac {1}{t}}}$. 取って${\displaystyle t}$- 分割グラフで、最小の唯一の部分を除くすべての部分のサイズが同じであり、部分のサイズは、総エッジ密度が${\displaystyle d}$。

のために${\displaystyle d\leq 1-{\frac {1}{r-1}}}$これにより、次のようなグラフが得られます。${\displaystyle (r-1)}$-partite なので、${\displaystyle K_{r}}$s.

下限は、三角形の場合についてRazborov (2008) ^{[ 10 ]によって証明され、後に Reiher (2016) [ 11 ]}によってすべてのクリークに一般化されました。上限は、Kruskal–Katona の定理^{[ 12 ]}の結果です。