禁止部分グラフ問題

トゥランの定理によれば、正の整数に対して${\displaystyle n,r}$満足${\displaystyle n\geq r\geq 3}$[ ^{3 ]​}${\textstyle \operatorname {ex} (n,K_{r})=\left(1-{\frac {1}{r-1}}+o(1)\right){\frac {n^{2}}{2}}.}$

これにより、禁止サブグラフ問題が解決されます。${\displaystyle G=K_{r}}$トゥランの定理の等号はトゥラングラフから得られる。${\displaystyle T(n,r-1)}$。

この結果は任意のグラフに一般化できる。${\displaystyle G}$色数を考慮すると${\displaystyle \chi (G)}$の${\displaystyle G}$。 ご了承ください${\displaystyle T(n,r)}$色を付けることができます${\displaystyle r}$色があり、したがって彩色数がより大きい部分グラフはありません${\displaystyle r}$。 特に、${\displaystyle T(n,\chi (G)-1)}$同型な部分グラフを持たない${\displaystyle G}$これは、禁止部分グラフ問題の一般的な等価ケースが、等価ケースと関連している可能性があることを示唆しています。${\displaystyle G=K_{r}}$この直感は、$\displaystyle o(n^{2})$エラー。

エルデシュ・ストーンの定理は、すべての正の整数に対して${\displaystyle n}$そしてすべてのグラフ${\displaystyle G}$[ ^{4 ]​}${\textstyle \operatorname {ex} (n,G)=\left(1-{\frac {1}{\chi (G)-1}}+o(1)\right){\binom {n}{2}}.}$

いつ${\displaystyle G}$は二部グラフではないので、これは の一次近似値を与える。${\displaystyle \operatorname {ex} (n,G)}$。

二部グラフの場合${\displaystyle G}$エルデシュ・ストーンの定理は、${\displaystyle \operatorname {ex} (n,G)=o(n^{2})}$二部グラフにおける禁止部分グラフ問題はザランキエヴィッチ問題として知られており、一般には未解決である。

ザランキエヴィッチ問題に関する進展には、以下の定理が含まれる。

クシュヴァーリ・ソス・トゥランの定理。正の整数のすべてのペアに対して${\displaystyle s,t}$と${\displaystyle t\geq s\geq 1}$ある定数が存在する${\displaystyle C}$（独立して）${\displaystyle n}$) のように${\textstyle \operatorname {ex} (n,K_{s,t})\leq Cn^{2-{\frac {1}{s}}}}$すべての正の整数に対して${\displaystyle n}$[ ^{5 ]​}

二部グラフに関するもう1つの結果は、偶数サイクルの場合である。${\displaystyle G=C_{2k},k\geq 2}$. サイクルも、ルート頂点とそこから分岐するパスを考慮することで処理されます。同じ長さのパスが 2 つある場合${\displaystyle k}$同じ終点を持ち、重複しない場合、長さのサイクルが作られます。${\displaystyle 2k}$これにより、次の定理が得られる。

定理（ボンディとシモノヴィッツ、1974年）。ある定数が存在する。${\displaystyle C}$そのため${\textstyle \operatorname {ex} (n,C_{2k})\leq Cn^{1+{\frac {1}{k}}}}$すべての正の整数に対して${\displaystyle n}$正の整数${\displaystyle k\geq 2}$[ ^{6 ]​}

極値グラフ理論における強力な補題の一つに、依存ランダム選択があります。この補題を用いることで、一方の部分の次数が制限されている二部グラフを扱うことができます。

定理（Alon、Krivelevich、およびSudakov、2003）。${\displaystyle G}$頂点部分を持つ二部グラフである${\displaystyle A}$そして${\displaystyle B}$すべての頂点が${\displaystyle A}$学位は最大で${\displaystyle r}$すると定数が存在する${\displaystyle C}$（${\displaystyle G}$) のように${\textstyle \operatorname {ex} (n,G)\leq Cn^{2-{\frac {1}{r}}}}$すべての正の整数に対して${\displaystyle n}$[ ^{7 ]​}

一般的に、我々は以下の推測を立てる。

有理指数予想（エルデシュとシモノヴィッツ）。任意の有限族に対して$\displaystyle {\mathcal {L}}}$グラフの場合、二部グラフが存在する場合${\displaystyle L\in {\mathcal {L}}}$すると、合理的な${\displaystyle \alpha \in [0,1)}$そのため${\displaystyle \operatorname {ex} (n,{\mathcal {L}})=\Theta (n^{1+\alpha })}$[ ^{8 ]​}

FürediとSimonovitsによる調査では、禁止部分グラフ問題に関する進展についてより詳細に説明されている。^{[ 8 ]}

この方法は主に弱い境界を与えるが、ランダムグラフの理論は急速に発展している分野である。これは、十分に小さな密度でランダムにグラフを取ると、グラフには少数のサブグラフしか含まれないという考えに基づいている。${\displaystyle G}$その内部。これらのコピーは、各コピーから 1 つのエッジを削除することによって削除できます。${\displaystyle G}$グラフでは、${\displaystyle G}$-無料グラフ。

確率的方法を用いて証明することができる${\displaystyle \operatorname {ex} (n,G)\geq cn^{2-{\frac {v(G)-2}{e(G)-1}}}}$どこ${\displaystyle c}$はグラフのみに依存する定数です${\displaystyle G}$。^{[ 9 ]}この構築のために、Erdős-Rényi ランダム グラフを使用できます。${\displaystyle G(n,p)}$つまり、グラフは${\displaystyle n}$頂点と辺は、確率で描画された任意の2つの頂点です${\displaystyle p}$独立して。期待されるコピー数を計算した後${\displaystyle G}$で${\displaystyle G(n,p)}$期待値の線形性により、各コピーから 1 つのエッジを削除します。${\displaystyle G}$そして私たちは${\displaystyle G}$最終的にグラフは自由になります。残るエッジの期待値は次のようになります。${\displaystyle \operatorname {ex} (n,G)\geq cn^{2-{\frac {v(G)-2}{e(G)-1}}}}$定数に対して${\displaystyle c}$に応じて${\displaystyle G}$したがって、少なくとも1つ${\displaystyle n}$-頂点グラフは、期待される数以上の辺を持つ。

この方法は、グラフの周長の上限に対するグラフの構成を見つけるためにも使用できます。周長は、で表されます。${\displaystyle g(G)}$はグラフの最短サイクルの長さです。なお、${\displaystyle g(G)>2k}$グラフは、以下の長さのサイクルをすべて禁止しなければならない。${\displaystyle 2k}$期待値の線形性により、このような禁止サイクルの期待値は、サイクルの期待値の合計に等しくなります。${\displaystyle C_{i}}$（のために${\displaystyle i=3,...,n-1,n}$。。。。再び禁止グラフの各コピーからエッジを削除し、より小さなサイクルのないグラフと${\displaystyle g(G)>2k}$私たちに${\displaystyle c_{0}n^{1+{\frac {1}{2k-1}}}}$グラフの左側の辺。

特定のケースでは、代数的構成を見つけることで改善がなされてきました。このような構成の共通の特徴は、幾何学を用いてグラフを構築することであり、頂点は幾何学的オブジェクトを表し、辺は頂点間の代数的関係に従います。結果として、部分グラフは得られません。${\displaystyle G}$純粋に幾何学的な理由から、グラフには多数のエッジがあり、接続の定義方法により強い境界となります。以下の証明は、Erdős、Rényi、およびSős ^{[ 10 ]}によるもので、下限を確立しています。${\displaystyle \operatorname {ex} (n,K_{2,2})}$として${\displaystyle \left({\frac {1}{2}}-o(1)\right)n^{3/2}}$これは、この方法の有効性を示している。

まず、${\displaystyle n=p^{2}-1}$一部のプライム${\displaystyle p}$極性グラフを考えてみましょう${\displaystyle G}$頂点要素を持つ${\displaystyle \mathbb {F} _{p}^{2}-\{0,0\}}$頂点間のエッジ${\displaystyle (x,y)}$そして${\displaystyle (a,b)}$かつその場合に限り${\displaystyle ax+by=1}$で$\displaystyle \mathbb {F} _{p}}$このグラフは${\displaystyle K_{2,2}}$-無料 なぜなら 2 つの線形方程式のシステム$\displaystyle \mathbb {F} _{p}}$解は1つしか持てません。頂点${\displaystyle (a,b)}$（仮定する${\displaystyle b\neq 0}$) は、${\displaystyle \left(x,{\frac {1-ax}{b}}\right)}$いかなる場合でも${\displaystyle x\in \mathbb {F} _{p}}$合計で少なくとも${\displaystyle p-1}$エッジ（1 を減算）${\displaystyle (a,b)=\left(x,{\frac {1-ax}{b}}\right)}$）だから少なくとも${\displaystyle {\frac {1}{2}}(p^{2}-1)(p-1)=\left({\frac {1}{2}}-o(1)\right)p^{3}=\left({\frac {1}{2}}-o(1)\right)n^{3/2}}$必要に応じてエッジを調整します。${\displaystyle n}$我々は${\displaystyle p=(1-o(1)){\sqrt {n}}}$と${\displaystyle p\leq {\sqrt {n+1}}}$（素数が存在するため、これは可能）${\displaystyle p}$間隔${\displaystyle [kk^{0.525},k]}$十分に大きい${\displaystyle k}$^{[ 11 ]} ) を用いて極性グラフを構築する${\displaystyle p}$加えて${\displaystyle np^{2}+1}$孤立した頂点は漸近値に影響を与えない。

以下の定理は、同様の結果である。${\displaystyle K_{3,3}}$。

定理（ブラウン、1966年）。${\displaystyle \operatorname {ex} (n,K_{3,3})\geq \left({\frac {1}{2}}-o(1)\right)n^{5/3}.}$^{[ 12 ]}

証明の概要。^{[ 13 ]}前の定理と同様に、${\displaystyle n=p^{3}}$プライム会員向け${\displaystyle p}$そして、グラフの頂点を、${\displaystyle \mathbb {F} _{p}^{3}}$今回は、頂点${\displaystyle (a,b,c)}$そして${\displaystyle (x,y,z)}$接続されているのは、${\displaystyle (x-a)^{2}+(y-b)^{2}+(z-c)^{2}=u}$で${\displaystyle \mathbb {F} _{p}}$特定の選ばれた人々のために${\displaystyle u}$それで、これは${\displaystyle K_{3,3}}$-自由です。なぜなら、3 つの球の交点には最大 2 つの点しか存在しないからです。したがって、${\displaystyle (x-a)^{2}+(y-b)^{2}+(z-c)^{2}}$ほぼ均一${\displaystyle \mathbb {F} _{p}}$各ポイントは約${\displaystyle p^{2}}$エッジの総数は${\displaystyle \left({\frac {1}{2}}-o(1)\right)p^{2}\cdot p^{3}=\left({\frac {1}{2}}-o(1)\right)n^{5/3}}$。

しかし、下限を厳しくすることは依然として未解決の問題である。${\displaystyle \operatorname {ex} (n,K_{t,t})}$のために${\displaystyle t\geq 4}$。

定理（Alon et al., 1999）${\displaystyle t\geq (s-1)!+1}$、${\displaystyle \operatorname {ex} (n,K_{s,t})=\Theta (n^{2-{\frac {1}{s}}}).}$^{[ 14 ]}

この手法は、上記の2つのアイデアを組み合わせたものです。ある代数集合に属する頂点間の接続を定義する際に、ランダムな多項式型の関係を使用します。この手法を用いて、次の定理を証明します。

定理：すべての${\displaystyle s\geq 2}$いくつか存在する${\displaystyle t}$そのため${\displaystyle \operatorname {ex} (n,K_{s,t})\geq \left({\frac {1}{2}}-o(1)\right)n^{2-{\frac {1}{s}}}}$。

証明の概要：最大の素数のべき乗を取ります${\displaystyle q}$と${\displaystyle q^{s}\leq n}$素数のギャップにより、${\displaystyle q=(1-o(1))n^{\frac {1}{s}}}$。 させて${\displaystyle f\in \mathbb {F} _{q}[x_{1},x_{2},\cdots ,x_{s},y_{1},y_{2},\cdots ,y_{s}]_{\leq d}}$ランダム多項式${\displaystyle \mathbb {F} _{q}}$学位取得まで${\displaystyle d=s^{2}}$で${\displaystyle X=(X_{1},X_{2},...,X_{s})}$そして${\displaystyle Y=(Y_{1},Y_{2},...,Y_{s})}$そして満足${\displaystyle f(X,Y)=f(Y,X)}$グラフを${\displaystyle G}$頂点セットを持つ${\displaystyle \mathbb {F} _{q}^{s}}$2つの頂点が${\displaystyle x,y}$隣接している場合${\displaystyle f(x,y)=0}$。

セットを固定します${\displaystyle U\subset \mathbb {F} _{q}^{s}}$集合を定義する${\displaystyle Z_{U}}$要素として${\displaystyle \mathbb {F} _{q}^{s}}$ない${\displaystyle U}$満足${\displaystyle f(x,u)=0}$すべての要素について${\displaystyle u\in U}$ラング・ワイル限界により、以下が得られる。${\displaystyle q}$十分に大きいので、${\displaystyle |Z_{U}|\leq C}$または${\displaystyle |Z_{U}|>{\frac {q}{2}}}$ある定数に対して${\displaystyle C}$.次に、期待される数を計算します。${\displaystyle U}$そのため${\displaystyle Z_{U}}$サイズがより大きい${\displaystyle C}$、そしてそのような各頂点から頂点を1つ削除する${\displaystyle U}$結果として得られるグラフは次のようになります。${\displaystyle K_{s,C+1}}$-自由であり、結果として得られるグラフのエッジ数の期待値を持つグラフが少なくとも1つ存在する。

トゥラン密度${\displaystyle h}$-一様グラフ${\displaystyle G}$と定義される

${\displaystyle \pi (G)=\lim _{n\to \infty }{\frac {\operatorname {ex} (n,G)}{\binom {n}{h}}}.}$

確かに${\displaystyle {\frac {\operatorname {ex} (n,G)}{\binom {n}{h}}}}$実際には正であり単調減少であるため、極限は必ず存在する。^{[ 15 ]}

例えば、トゥランの定理によれば、${\displaystyle \pi (K_{r+1})=1-{\frac {1}{r}}}$、エルデシュ・ストーンの定理によれば、${\displaystyle \pi (G)=1-{\frac {1}{\chi (H)-1}}}$特に、二部グラフの場合${\displaystyle G}$、${\displaystyle \pi (G)=0}$。トゥラン密度の決定${\displaystyle \pi (H)}$決定することと同等${\displaystyle \operatorname {ex} (n,G)}$最大${\displaystyle o(n^{2})}$エラー。^{[ 16 ]}

を考えて${\displaystyle h}$-一様ハイパーグラフ${\displaystyle H}$と${\displaystyle v(H)}$頂点。過飽和定理によれば、すべての頂点に対して、${\displaystyle \epsilon >0}$存在する${\displaystyle \delta >0}$もし${\displaystyle G}$は${\displaystyle h}$-一様ハイパーグラフ${\displaystyle n}$頂点と少なくとも${\displaystyle (\pi (H)+\epsilon ){\binom {n}{h}}}$エッジ${\displaystyle n}$十分に大きい場合、少なくとも${\displaystyle \delta n^{v(H)}}$コピー${\displaystyle H}$[ ^{17 ]​}

同様に、この定理は次のように言い換えることができます。グラフが${\displaystyle G}$と${\displaystyle n}$頂点には${\displaystyle o(n^{v(H)})}$コピー${\displaystyle H}$そうすれば最大で${\displaystyle \pi (H){\binom {n}{2}}+o(n^{2})}$エッジ${\displaystyle G}$。

過飽和型問題を考察することで、様々な禁止部分グラフ問題を解決できる可能性がある。以下に、Kővári–Sós–Turánの定理を再述し、その証明の概略を示す。

クシュヴァーリ・ソス・トゥランの定理。正の整数のすべてのペアに対して${\displaystyle s,t}$と${\displaystyle t\geq s\geq 1}$ある定数が存在する${\displaystyle C}$（独立して）${\displaystyle n}$) のように${\textstyle \operatorname {ex} (n,K_{s,t})\leq Cn^{2-{\frac {1}{s}}}}$すべての正の整数に対して${\displaystyle n}$[ ^{18 ]​}

証明。${\displaystyle G}$になる${\displaystyle 2}$-グラフ${\displaystyle n}$頂点、そしてコピーの数を考慮する${\displaystyle K_{1,s}}$で${\displaystyle G}$次数が与えられた頂点${\displaystyle d}$正確に${\displaystyle {\binom {d}{s}}}$コピー${\displaystyle K_{1,s}}$この頂点を根として、合計${\displaystyle \sum _{v\in V(G)}{\binom {\operatorname {deg} (v)}{s}}}$コピー。ここに、${\displaystyle {\binom {k}{s}}=0}$いつ${\displaystyle 0\leq k<s}$凸性により、合計で少なくとも${\displaystyle n{\binom {2e(G)/n}{s}}}$コピー${\displaystyle K_{1,s}}$さらに、明らかに${\displaystyle {\binom {n}{s}}}$サブセット${\displaystyle s}$頂点の数より多い場合は${\displaystyle (t-1){\binom {n}{s}}}$コピー${\displaystyle K_{1,s}}$すると鳩の巣原理によ​​り、次の部分集合が存在するはずである${\displaystyle s}$少なくとも の葉の集合を形成する頂点${\displaystyle t}$これらのコピーから、${\displaystyle K_{s,t}}$したがって、${\displaystyle K_{s,t}}$私たちが持っている限り${\displaystyle n{\binom {2e(G)/n}{s}}>(t-1){\binom {n}{s}}}$言い換えれば、次のような事象が発生します。${\displaystyle {\frac {e(G)^{s}}{n^{s-1}}}\geq O(n^{s})}$、これは以下のように簡略化されます。${\displaystyle e(G)\geq O(n^{2-{\frac {1}{s}}})}$これは定理の記述である。^{[ 19 ]}

この証明では、より小さな部分グラフの出現回数を考慮することで、過飽和法を使用しています。通常、過飽和法の応用では過飽和定理は使用されません。代わりに、多くの場合、部分グラフを見つけることが構造に関わってきます。${\displaystyle H'}$禁止された部分グラフの${\displaystyle H}$そして、それが何度も現れると、${\displaystyle G}$、 それから${\displaystyle H}$必ず表示されなければならない${\displaystyle G}$同様に、過飽和法で解決できる禁止部分グラフ問題に関するその他の定理には、以下のようなものがある。