Fraction of graph maps that are homomorphisms
極値グラフ理論 という 数学の 分野では 、 グラフに関する 準同型密度は 、次のように 各グラフに関連付けられた パラメータです。 H {\displaystyle H} t ( H , − ) {\displaystyle t(H,-)} G {\displaystyle G}
t ( H , G ) := | hom ( H , G ) | | V ( G ) | | V ( H ) | {\displaystyle t(H,G):={\frac {\left|\operatorname {hom} (H,G)\right|}{|V(G)|^{|V(H)|}}}} 。 上図は、 グラフ準同型写像 、つまり からへ の隣接関係保存写像 の集合である。密度は、 の頂点から 一様ランダムに選ばれた の頂点への 写像がグラフ準同型である確率とも解釈できる。 [1] 準同型写像密度と部分グラフ密度の間には関連があり、これについては以下で詳しく説明する。 [2] hom ( H , G ) {\displaystyle \operatorname {hom} (H,G)} H {\displaystyle H} G {\displaystyle G} H {\displaystyle H} G {\displaystyle G}
例 グラフの辺密度は 次のように与えられ ます G {\displaystyle G} t ( K 2 , G ) {\displaystyle t(K_{2},G)} ステップ を伴う歩行の数はによって与えられます 。 k − 1 {\displaystyle k-1} hom ( P k , G ) {\displaystyle \operatorname {hom} (P_{k},G)} hom ( C k , G ) = Tr ( A k ) {\displaystyle \operatorname {hom} (C_{k},G)=\operatorname {Tr} (A^{k})} ここで は の隣接行列です 。 A {\displaystyle A} G {\displaystyle G} 適切な色 を使用した着色の割合は で与えられます 。 k {\displaystyle k} t ( G , K k ) {\displaystyle t(G,K_{k})} 安定集合の数や最大カットなどの他の重要な性質は、準同型数や密度で表現または推定することができます。 [3]
部分グラフ密度 の（ラベル付き）部分グラフ密度を次のように定義 し ます H {\displaystyle H} G {\displaystyle G}
d ( H , G ) := # labeled copies of H in G | V ( G ) | | V ( H ) | {\displaystyle d(H,G):={\frac {\#{\text{ labeled copies of }}H{\text{ in }}G}{|V(G)|^{|V(H)|}}}} 。 の頂点上 のラベル付き部分グラフの総数で完全に割り切れるわけではないため、これを密度と呼ぶのは少し疑わしいかもしれませんが、 私たちの定義は漸近的に同値であり、私たちの目的のためには分析が簡単です。 におけるの任意のラベル付きコピーは、 へ の の準同型に対応することに注意してください。ただし、すべての準同型がラベル付きコピーに対応するわけではありません。 の複数の頂点が の同じ頂点に送られる 、退化したケースもあります 。とはいえ、そのような退化した準同型の数は だけな ので、 となります 。例えば、一定の準同型密度を持つグラフの場合、ラベル付き部分グラフ密度と準同型密度は漸近的に同値であることがわかります。 は 完全グラフであるため、 の辺は グラフ準同型の下でのすべての像を異なるものにする
ため、 準同型密度と部分グラフ密度は実際には等しくなります（ 自己ループなしの場合） 。 | V ( H ) | {\displaystyle |V(H)|} G {\displaystyle G} H {\displaystyle H} G {\displaystyle G} H {\displaystyle H} G {\displaystyle G} H {\displaystyle H} G {\displaystyle G} O ( n | V ( H ) | − 1 ) {\displaystyle O(n^{|V(H)|-1})} t ( H , G ) = d ( H , G ) + O ( 1 / n ) {\displaystyle t(H,G)=d(H,G)+O(1/n)} H {\displaystyle H} K m {\displaystyle K_{m}} G {\displaystyle G} K m {\displaystyle K_{m}}
グラフオンへの一般化 準同型密度の概念は、グラフの代わりにグラフ オン がある 場合に一般化できます G {\displaystyle G} W {\displaystyle W}
t ( H , W ) = ∫ [ 0 , 1 ] | V ( H ) | ∏ i j ∈ E ( H ) W ( x i , x j ) ∏ i ∈ V ( H ) d x i {\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}} 積分関数は部分グラフの辺をまたぐ積である のに対し、微分関数はグラフの頂点をまたぐ積であることに注意する。直感的には、 グラフの 各頂点 は変数で表される。 例えば、グラフオンの三角形の密度は次のように表される。 H {\displaystyle H} H {\displaystyle H} i {\displaystyle i} H {\displaystyle H} x i . {\displaystyle x_{i}.}
t ( K 3 , W ) = ∫ [ 0 , 1 ] 3 W ( x , y ) W ( y , z ) W ( z , x ) d x d y d z {\displaystyle t(K_{3},W)=\int \limits _{[0,1]^{3}}W(x,y)W(y,z)W(z,x)dxdydz} 。 この準同型密度の定義は、あらゆるグラフとそれに関連するステップグラフンに対して 、 となるため、まさに一般化である 。 [1] G {\displaystyle G} W G {\displaystyle W_{G}} t ( H , G ) = t ( H , W G ) {\displaystyle t(H,G)=t(H,W_{G})}
この定義は、すべての対称かつ測定可能な関数 にさらに拡張できます 。次の例は、このさらなる一般化の利点を示しています。関数 に対する における の 密度は、 における オイラー閉路 の数です 。 W {\displaystyle W} W ( x , y ) = 2 cos ( 2 π ( x − y ) ) {\displaystyle W(x,y)=2\cos(2\pi (x-y))} H {\displaystyle H} W {\displaystyle W} H {\displaystyle H}
グラフオンはグラフのシーケンスの極限であるため、この概念は、特定のプロパティを満たすグラフの準同型密度の漸近的な動作を理解するのに役立ちます。
不平等 極値グラフ理論 における多くの結果は、 グラフに付随する準同型密度を含む不等式によって記述できます。以下は、三角形の密度と辺の密度を関連付ける一連の例です。
トゥランの定理 典型的な例は トゥランの定理 で、ならば と なります 。 この特別な例は マンテルの定理 で、 ならば と なります t ( K r , W ) = 0 {\displaystyle t(K_{r},W)=0} t ( K 2 , W ) ≤ ( 1 − 1 r − 1 ) {\displaystyle t(K_{2},W)\leq \left(1-{\frac {1}{r-1}}\right)} t ( K 3 , W ) = 0 {\displaystyle t(K_{3},W)=0} t ( K 2 , W ) ≤ 1 / 2 {\displaystyle t(K_{2},W)\leq 1/2}
グッドマンの定理 マンテルの定理の拡張は、辺密度の観点から三角形の密度の明確な下限値を提供します。 [3]
定理（グッドマン） t ( K 3 , G ) ≥ t ( K 2 , G ) ( 2 t ( K 2 , G ) − 1 ) . {\displaystyle t(K_{3},G)\geq t(K_{2},G)(2t(K_{2},G)-1).}
クラスカル・カトーナ定理 グッドマンの定理の逆不等式は、 と述べる クラスカル・カトーナ定理 の特殊なケースです。これらの不等式はどちらも、特定の辺密度に対して厳密に成り立つことがわかります。 t ( K 3 , G ) ≤ t ( K 2 , G ) 3 / 2 {\displaystyle t(K_{3},G)\leq t(K_{2},G)^{3/2}}
証明： 任意のグラフ に対してこの不等式を証明すれば十分である 。 は頂点 上 のグラフであり 、はその 隣接行列 の固有値であるとする 。 スペクトルグラフ理論 により、 G {\displaystyle G} G {\displaystyle G} n {\displaystyle n} { λ i } i = 1 n {\displaystyle \{\lambda _{i}\}_{i=1}^{n}} A G {\displaystyle A_{G}}
hom ( K 2 , G ) = t ( K 2 , G ) | V ( G ) | 2 = ∑ i = 1 n λ i 2 {\displaystyle \operatorname {hom} (K_{2},G)=t(K_{2},G)|V(G)|^{2}=\sum _{i=1}^{n}\lambda _{i}^{2}} 、 そして 。 hom ( K 3 , G ) = t ( K 3 , G ) | V ( G ) | 3 = ∑ i = 1 n λ i 3 {\displaystyle \operatorname {hom} (K_{3},G)=t(K_{3},G)|V(G)|^{3}=\sum _{i=1}^{n}\lambda _{i}^{3}} すると、次の不等式から結論が導き出されます。
hom ( K 3 , G ) = ∑ i = 1 n λ i 3 ≤ ( ∑ i = 1 n λ i 2 ) 3 / 2 = hom ( K 2 , G ) 3 / 2 {\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] t ( K 3 , G ) {\displaystyle t(K_{3},G)} t ( K 2 , G ) {\displaystyle t(K_{2},G)} D 2 , 3 {\displaystyle D_{2,3}}
D 2 , 3 = { ( t ( K 2 , W ) , t ( K 3 , W ) ) : W is a graphon } ⊆ [ 0 , 1 ] 2 {\displaystyle D_{2,3}=\{(t(K_{2},W),t(K_{3},W))\;:\;W{\text{ is a graphon}}\}\subseteq [0,1]^{2}} 。
この領域の上限は厳密であり、クラスカル・カトーナ定理によって与えられます。下限は、ラズボロフによる完全な記述の主要な成果です。 [4]
コーシー・シュワルツ 準同型密度を解析するのに特に便利な不等式の一つは、 コーシー・シュワルツ不等式 です。コーシー・シュワルツ不等式を適用すると、グラフを対称線で「折り畳んで」、より小さなグラフに関連付けることができます。これにより、大きくても対称的なグラフの密度を、より小さなグラフの密度に縮小することができます。例として、長さ4の閉路が シドレンコ閉路で あることを証明します。頂点に1、2、3、4の順序でラベルを付けると、頂点1と3を通る対角線は対称線になります。この線で折り畳むと、 完全な 二部グラフ になります。数学的には、これは次のように形式化されます C 4 {\displaystyle C_{4}} K 1 , 2 {\displaystyle K_{1,2}}
t ( C 4 , G ) = ∫ 1 , 2 , 3 , 4 W ( 1 , 2 ) W ( 2 , 3 ) W ( 3 , 4 ) W ( 1 , 4 ) = ∫ 1 , 3 ( ∫ 2 W ( 1 , 2 ) W ( 2 , 3 ) ) ( ∫ 4 W ( 1 , 4 ) W ( 4 , 3 ) ) = ∫ 1 , 3 ( ∫ 2 W ( 1 , 2 ) W ( 2 , 3 ) ) 2 ≥ ( ∫ 1 , 2 , 3 W ( 1 , 2 ) W ( 2 , 3 ) ) 2 = t ( K 1 , 2 , G ) 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 に「折り畳む」ことにしました。同じ手法を使用して を示すことができ 、これを上記と組み合わせると が シドレンコ グラフであることが証明されます。 t ( K 1 , 2 , G ) ≥ t ( K 2 , G ) 2 {\displaystyle t(K_{1,2},G)\geq t(K_{2},G)^{2}} C 4 {\displaystyle C_{4}}
一般化された ヘルダー不等式 も同様の方法で、グラフを1回のステップで複数回折り畳むことができます。また、特定の辺が対称軸上にある場合のグラフの折り畳みには、より一般的な形のコーシー・シュワルツ不等式を適用することも可能です。
ラグランジアン ラグランジアンは極値問題の解析に役立ちます。その量は次のように定義されます
L ( H ) = max x 1 , … , x n ≥ 0 x 1 + ⋯ x n = 1 ∑ e ∈ E ( H ) ∏ v ∈ e x v {\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}} 。 有用な事実の一つは、最大化ベクトルが クリークの頂点上で均等に支持されるということです 。以下は、この量の解析の応用です。 x {\displaystyle x} H {\displaystyle H}
ハメド・ハタミとセルゲイ・ノリンによれば、準同型密度間の任意の代数的不等式は線型不等式に変換できる。 [2] 状況によっては、そのような不等式が真であるかどうかの判断は、次の定理のように単純化できる。
定理（ ボロバス ）。 実定数をとし ます。すると、不等式 a 1 , ⋯ , a n {\displaystyle a_{1},\cdots ,a_{n}}
∑ i = 1 n a i t ( K i , G ) ≥ 0 {\displaystyle \sum _{i=1}^{n}a_{i}t(K_{i},G)\geq 0} あらゆるグラフに対して が成り立つ とき、そして があらゆる完全グラフに対して が成り立つときのみに限る 。 [5] G {\displaystyle G} K m {\displaystyle K_{m}}
しかし、より一般的なグラフの集合上に準同型不等式がある場合、 はるかに難しい問題、実際には 決定不可能な 問題が発生します。 H i {\displaystyle H_{i}}
定理（ハタミ、ノリン）。 実定数とグラフを仮定する 。 このとき、準同型密度不等式が成立するかどうかは決定不可能な問題である。 a 1 , ⋯ , a n {\displaystyle a_{1},\cdots ,a_{n}} { H i } i = 1 n {\displaystyle \{H_{i}\}_{i=1}^{n}}
∑ i = 1 n a r t ( H i , G ) ≥ 0 {\displaystyle \sum _{i=1}^{n}a_{r}t(H_{i},G)\geq 0} あらゆるグラフに対して成り立つ 。 [2] G {\displaystyle G}
最近の観察 [6] は、任意の線形準同型密度不等式は、ある無限行列の半正定値性、または 量子グラフ の正値性の結果であることが証明されている。言い換えれば、そのような不等式はコーシー・シュワルツ不等式の応用から導かれる。 [2]
参照
参考文献 ^ ab Borgs, Christian; Chayes, Jennifer T.; Lovász, László ; Sós, Vera T .; Vestergombi, Katalin (2008). 「Convergent sequence of dense graphs. I. Subgraph frequents, metric properties and testing」. Advances in Mathematics . 219 (6): 1801– 1851. arXiv : math/0702004 . doi : 10.1016/j.aim.2008.07.008 . ^ abcd Hatami, H., Norine, S. (2011). 「グラフ準同型密度における線形不等式の決定不可能性」 (PDF) . Journal of the American Mathematical Society . 24 (2): 553. arXiv : 1005.2382 . doi :10.1090/S0894-0347-2010-00687-X. S2CID 3363894 – MathSciNet経由. {{cite journal }}: CS1 maint: multiple names: authors list (link )^ ab Lovász、László (2012). 大規模なネットワークとグラフの制限 。ロードアイランド州プロビデンス。 ISBN 978-0-8218-9085-1 OCLC 812530987 {{cite book }}: CS1 maint: location missing publisher (link )^ ab Razborov, Alexander (2008). 「グラフにおける三角形の最小密度について」 (PDF) . Combinatorics, Probability and Computing . 17 (4): 603– 618. doi :10.1017/S0963548308009085. S2CID 26524353 – MathSciNet (AMS) 経由 ^ Bollobás, Bela (1986). 組合せ論：集合系、ハイパーグラフ、ベクトル族、組合せ確率. ケンブリッジ：ケンブリッジ大学出版局. pp. 79-84. ISBN 0-521-33059-9 。 ^ Freedman, M., Lovász, L., Schrijver, A. (2007). 「鏡映正値性、ランク連結性、およびグラフの準同型性」 (PDF) . アメリカ数学会誌 . 20 (1): 1 {{cite journal }}: CS1 maint: multiple names: authors list (link )
![{\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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12b5319ba50351e6aff99922fc4124ad5d369a00)
![{\displaystyle t(K_{3},W)=\int \limits _{[0,1]^{3}}W(x,y)W(y,z)W(z,x)dxdydz}](https://wikimedia.org/api/rest_v1/media/math/render/svg/069fd05db20ade314b79abefbc59aaabcff146d3)
![{\displaystyle D_{2,3}=\{(t(K_{2},W),t(K_{3},W))\;:\;W{\text{はグラフオン}}\}\subseteq [0,1]^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/98fc38371573902fcd8f17b97b5b08a583f62089)
