準同型密度

極値グラフ理論という数学の分野では、グラフに関する準同型密度は、次のように 各グラフに関連付けられるパラメータです。${\displaystyle H}$${\displaystyle t(H,-)}$${\displaystyle G}$

${\displaystyle t(H,G):={\frac {\left|\operatorname {hom} (H,G)\right|}{|V(G)|^{|V(H)|}}}}$。

上記は、からへのグラフ準同型写像、または隣接関係保存写像の集合です。密度は、一様ランダムに選ばれたの頂点から の頂点への写像がグラフ準同型である確率として解釈することもできます。 ^[1]準同型写像密度とサブグラフ密度の間には関連があり、これについては以下で詳しく説明します。^[2]${\displaystyle \operatorname {hom} (H,G)}$${\displaystyle H}$${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$

• グラフのエッジ密度は で与えられます。${\displaystyle G}$${\displaystyle t(K_{2},G)}$
• ステップを伴う歩行の数はで与えられます。${\displaystyle k-1}$${\displaystyle \operatorname {hom} (P_{k},G)}$
• ${\displaystyle \operatorname {hom} (C_{k},G)=\operatorname {Tr} (A^{k})}$ここで はの隣接行列です。${\displaystyle A}$${\displaystyle G}$
• 適切な色を使用した着色の割合は で与えられます。${\displaystyle k}$${\displaystyle t(G,K_{k})}$

安定集合の数や最大カットなどの他の重要な性質は、準同型数や密度によって表現または推定することができます。^[3]

の（ラベル付き）サブグラフ密度を次のように 定義する。${\displaystyle H}$${\displaystyle G}$

${\displaystyle d(H,G):={\frac {\#{\text{ }}G 内の }}H{\text{ のラベル付きコピー}{|V(G)|^{|V(H)|}}}}$。

なお、これを密度と呼ぶのはやや疑わしいかもしれません。なぜなら、を の頂点上のラベル付きサブグラフの総数で完全に割り切れるわけではないからです。しかし、私たちの定義は漸近的に同値であり、私たちの目的のためには分析がより簡単になります。における の任意のラベル付きコピーはの への準同型に対応することに注目してください。しかし、すべての準同型がラベル付きコピーに対応するわけではありません。 の複数の頂点が の同じ頂点に送信される、退化したケースがいくつかあります。そうは言っても、そのような退化した準同型の数は だけなので、 となります。たとえば、一定の準同型密度を持つグラフの場合、ラベル付きサブグラフ密度と準同型密度は漸近的に同値であることがわかります。は完全グラフ であるため、準同型密度とサブグラフ密度は実際には等しくなります (自己ループなしの場合)。これは、 の辺により、グラフ準同型の下でのすべての像が別個になるように強制されるためです。 ${\displaystyle |V(H)|}$${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle O(n^{|V(H)|-1})}$${\displaystyle t(H,G)=d(H,G)+O(1/n)}$${\displaystyle H}$${\displaystyle K_{m}}$${\displaystyle G}$${\displaystyle K_{m}}$

準同型密度の概念は、グラフの代わりにグラフオンがある場合に一般化できる。 ${\displaystyle G}$ ${\displaystyle W}$

${\displaystyle t(H,W)=\int _{[0,1]^{|V(H)|}}\prod _{ij\in E(H)}W(x_{i},x_{j})\prod _{i\in V(H)}dx_{i}}$

積分関数はサブグラフ の辺をまたぐ積であるのに対し、微分は の頂点をまたぐ積であることに注意する。直感的には、の各頂点は変数 で表される。 たとえば、グラフオン の三角形の密度は次のように表される。 ${\displaystyle H}$${\displaystyle H}$${\displaystyle i}$${\displaystyle H}$${\displaystyle x_{i}.}$

${\displaystyle t(K_{3},W)=\int \limits _{[0,1]^{3}}W(x,y)W(y,z)W(z,x)dxdydz}$。

この準同型密度の定義は、あらゆるグラフとそれに関連するステップグラフンに対して、 となるため、まさに一般化である。^[1]${\displaystyle G}$${\displaystyle W_{G}}$${\displaystyle t(H,G)=t(H,W_{G})}$

定義は、すべての対称で測定可能な関数 にさらに拡張できます。次の例は、この一般化の利点を示しています。関数 を基準として、におけるの密度は、におけるオイラー閉路の数です。 ${\displaystyle W}$${\displaystyle W(x,y)=2\cos(2\pi (xy))}$${\displaystyle H}$${\displaystyle W}$${\displaystyle H}$

グラフオンはグラフのシーケンスの極限であるため、この概念は、特定のプロパティを満たすグラフの準同型密度の漸近的な動作を理解するのに役立ちます。

極値グラフ理論における多くの結果は、グラフに関連付けられた準同型密度を含む不等式によって記述できます。以下は、三角形の密度とエッジの密度を関連付ける一連の例です。

典型的な例は、 ならば であると述べるトゥランの定理 です。この定理の特殊なケースは、ならば であると述べるマンテルの定理です。 ${\displaystyle t(K_{r},W)=0}$${\displaystyle t(K_{2},W)\leq \left(1-{\frac {1}{r-1}}\right)}$${\displaystyle t(K_{3},W)=0}$${\displaystyle t(K_{2},W)\leq 1/2}$

マンテルの定理の拡張は、辺密度の観点から三角形の密度の明確な下限値を提供します。^[3]

定理（グッドマン）。 ${\displaystyle t(K_{3},G)\geq t(K_{2},G)(2t(K_{2},G)-1).}$

グッドマンの定理の逆不等式は、 と述べているクラスカル・カトーナの定理の特殊なケースです。これらの不等式は両方とも、特定のエッジ密度に対して厳密であることがわかります。 ${\displaystyle t(K_{3},G)\leq t(K_{2},G)^{3/2}}$

証明。 任意のグラフ に対してこの不等式を証明すれば十分です。は頂点上のグラフであり、 は隣接行列の固有値であるとします。スペクトルグラフ理論により、次のことがわかります。 ${\displaystyle G}$${\displaystyle G}$${\displaystyle n}$${\displaystyle \{\lambda_{i}\}_{i=1}^{n}}$ ${\displaystyle A_{G}}$

${\displaystyle \operatorname {hom} (K_{2},G)=t(K_{2},G)|V(G)|^{2}=\sum _{i=1}^{n}\lambda _{i}^{2}}$、 そして。${\displaystyle \operatorname {hom} (K_{3},G)=t(K_{3},G)|V(G)|^{3}=\sum _{i=1}^{n}\lambda _{i}^{3}}$

すると、次の不等式から結論が導き出されます。

${\displaystyle \operatorname {hom} (K_{3},G)=\sum _{i=1}^{n}\lambda _{i}^{3}\leq \left(\sum _{i=1}^{n}\lambda _{i}^{2}\right)^{3/2}=\operatorname {hom} (K_{2},G)^{3/2}}$。

と の関係のより完全な記述は、ラズボロフによって証明されました。彼の 2008 年の研究は、準同型不等式問題、つまりグラフオンにおける実行可能な辺密度、三角形密度のペアの領域である の記述の理解を完了しました。^[4]${\displaystyle t(K_{3},G)}$${\displaystyle t(K_{2},G)}$${\displaystyle D_{2,3}}$

${\displaystyle D_{2,3}=\{(t(K_{2},W),t(K_{3},W))\;:\;W{\text{ はグラフオン}}\}\subseteq [0,1]^{2}}$。

領域の上限は厳密であり、クラスカル・カトーナ定理によって与えられます。下限は、完全な記述を提供するラズボロフの研究の主な結果です。^[4]

準同型密度を分析するのに特に便利な不等式は、コーシー・シュワルツ不等式です。コーシー・シュワルツ不等式を適用すると、グラフを対称線で「折り畳んで」、より小さなグラフに関連付けることができます。これにより、大きくても対称的なグラフの密度を、より小さなグラフの密度に縮小できます。例として、長さ 4 のサイクルがシドレンコであることを証明します。頂点にこの順序で 1、2、3、4 のラベルが付けられている場合、頂点 1 と 3 を通る対角線は対称線です。この線で折り畳むと、完全な2 部グラフに関連します。数学的には、これは次のように形式化されます。 ${\displaystyle C_{4}}$ ${\displaystyle K_{1,2}}$

${\displaystyle {\begin{aligned}t(C_{4},G)&=\int _{1,2,3,4}W(1,2)W(2,3)W(3,4)W(1,4)=\int _{1,3}\left(\int _{2}W(1,2)W(2,3)\right)\left(\int _{4}W(1,4)W(4,3)\right)=\int _{1,3}\left(\int _{2}W(1,2)W(2,3)\right)^{2}\\&\geq \left(\int _{1,2,3}W(1,2)W(2,3)\right)^{2}=t(K_{1,2},G)^{2}\end{aligned}}}$

ここで、コーシー・シュワルツ法を適用して頂点 2 を頂点 4 に「折り畳む」。同じ手法を使用して を示すことができ、これを上記と組み合わせると がシドレンコ グラフであることが証明される。 ${\displaystyle t(K_{1,2},G)\geq t(K_{2},G)^{2}}$${\displaystyle C_{4}}$

一般化されたヘルダーの不等式も同様の方法で使用して、1 つのステップでグラフを複数回折りたたむことができます。特定のエッジが対称線上にある場合に、より一般的な形式のコーシー・シュワルツを適用してグラフを折りたたむこともできます。

ラグランジアンは極限問題を解析する際に役立ちます。その量は次のように定義されます。

${\displaystyle L(H)=\max _{\begin{matrix}x_{1},\ldots ,x_{n}\geq 0\\x_{1}+\cdots x_{n}=1\end{matrix}}\sum _{e\in E(H)}\prod _{v\in e}x_{v}}$。

1 つの有用な事実は、最大化ベクトルが内のクリークの頂点上で均等にサポートされていることです。以下は、この量を分析する応用です。 ${\displaystyle x}$${\displaystyle H}$

ハメド・ハタミとセルゲイ・ノリンによれば、準同型密度間の任意の代数的不等式を線型不等式に変換することができる。^[2]状況によっては、そのような不等式が真であるかどうかの判断は、次の定理の場合のように単純化できる。

定理（ボロバス）。実定数をとします。すると、不等式 ${\displaystyle a_{1},\cdots ,a_{n}}$

${\displaystyle \sum _{i=1}^{n}a_{i}t(K_{i},G)\geq 0}$

あらゆるグラフに対して成り立つのは、あらゆる完全グラフに対して成り立つ場合のみである。^[5]${\displaystyle G}$${\displaystyle K_{m}}$

しかし、より一般的なグラフの集合上に準同型不等式がある場合 、はるかに難しい問題、実際には決定不可能な問題が発生します。${\displaystyle H_{i}}$

定理（ハタミ、ノリン）。 を実定数、グラフとする。このとき、準同型密度不等式が成立するかどうかは決定不可能な問題である。 ${\displaystyle a_{1},\cdots ,a_{n}}$${\displaystyle \{H_{i}\}_{i=1}^{n}}$

${\displaystyle \sum _{i=1}^{n}a_{r}t(H_{i},G)\geq 0}$

あらゆるグラフに対して成り立つ。^[2]${\displaystyle G}$

最近の観察^[6]は、任意の線形準同型密度不等式は、ある無限行列の半正定値性、または量子グラフの正値性の結果であることを証明しています。言い換えれば、そのような不等式はコーシー・シュワルツ不等式の応用から導かれます。^[2]

• 共通グラフ
• シドレンコの予想