シドレンコの予想

シドレンコ予想は、1986 年にアレクサンダー シドレンコによって提起された極限グラフ理論の分野における主要な予想です。大まかに言えば、この予想は、平均次数 の頂点上の任意の2 部グラフおよびグラフに対して、小さな誤差項を除いて、にのラベル付きコピーが少なくとも存在するというものです。正式には、グラフオンにおけるグラフ準同型密度に関する直感的な不等式を提供します。この予想された不等式は、各辺が確率 で存在する場合、可能性のあるサブグラフの一部が のコピーであると予想されるため、グラフにおける のコピーの密度はランダム グラフによって漸近的に最小化されるというステートメントとして解釈できます。 ${\displaystyle H}$ ${\displaystyle G}$${\displaystyle n}$${\displaystyle pn}$${\displaystyle p^{|E(H)|}n^{|V(H)|}}$${\displaystyle H}$${\displaystyle G}$${\displaystyle H}$${\displaystyle p^{|E(H)|}}$${\displaystyle H}$${\displaystyle p}$

をグラフとする。このとき、すべてのグラフオンに対して不等式 ${\displaystyle H}$${\displaystyle H}$ ${\displaystyle W}$

${\displaystyle t(H,W)\geq t(K_{2},W)^{|E(H)|}}$

は真であり、 はにおけるの準同型密度です。 ${\displaystyle t(H,W)}$${\displaystyle H}$${\displaystyle W}$

シドレンコ予想（1986）は、すべての二部グラフはシドレンコの性質を持つと述べている。^[1]

がグラフ である場合、これは からへの一様ランダム写像が準同型である確率が、 の各辺について、その辺が の辺に写像される確率の積以上であることを意味します。これは、おおよそ、固定数の頂点と平均次数を持つランダムに選択されたグラフには、 のラベル付きコピーが最小数存在することを意味します。不等式の右辺は、各辺写像が独立している場合に写像が準同型である確率であるため、これは驚くべき推測ではありません。したがって、2 つの辺は少なくとも同じ順序であると予想されます。グラフオンへの自然な拡張は、すべてのグラフオンがグラフのいくつかのシーケンスの極限点であるという事実から得られます。 ${\displaystyle W}$${\displaystyle G}$${\displaystyle V(H)}$${\displaystyle V(G)}$${\displaystyle H}$${\displaystyle G}$${\displaystyle H}$

が二部グラフである場合、シドレンコの性質を持つという要件は必須です。つまり、 が二部グラフである場合、 は三角形がないのでとなります。しかし、は の辺の数の 2 倍であるため、 に対してシドレンコの性質は成り立ちません。同様の議論から、奇数サイクルを持つグラフにはシドレンコの性質がないことがわかります。グラフが二部であるためには奇数サイクルが存在しない必要があります。したがって、シドレンコの性質を持つ可能性のあるグラフは二部グラフのみであることを意味します。 ${\displaystyle H}$${\displaystyle W}$${\displaystyle t(K_{3},W)=0}$${\displaystyle W}$${\displaystyle t(K_{2},W)}$${\displaystyle W}$${\displaystyle K_{3}}$

シドレンコの性質は、次の定式化と同等です。

すべてのグラフ について、に頂点があり、平均次数がである場合、 となります。${\displaystyle G}$${\displaystyle G}$${\displaystyle n}$${\displaystyle pn}$${\displaystyle t(H,G)\geq p^{|E(H)|}}$

これは、から への準同型の数がの辺の数の 2 倍であり、不等式は、前述のように がグラフである場合にのみチェックする必要があるため、同等です。 ${\displaystyle K_{2}}$${\displaystyle G}$${\displaystyle G}$${\displaystyle W}$

この定式化では、から への非単射準同型の数は最大で の定数倍であるため、シドレンコの性質は、にのラベル付きコピーが少なくとも 個存在することを意味します。 ${\displaystyle H}$${\displaystyle G}$${\displaystyle n^{|V(H)|-1}}$${\displaystyle (p^{|E(H)|}-o(1))n^{|V(H)|}}$${\displaystyle H}$${\displaystyle G}$

前述のように、シドレンコの性質を証明するには、すべてのグラフ に対して不等式 を示せば十分です。このセクション全体を通じて、は平均次数 の頂点上のグラフです。 量はからへの準同型性の数を指します。この量は と同じです。 ${\displaystyle G}$${\displaystyle G}$${\displaystyle n}$${\displaystyle pn}$${\displaystyle \operatorname {hom} (H,G)}$${\displaystyle H}$${\displaystyle G}$${\displaystyle n^{|V(H)|}t(H,G)}$

いくつかのグラフに対するシドレンコの性質の基本的な証明は、コーシー・シュワルツの不等式またはヘルダーの不等式から得られます。その他の証明は、スペクトルグラフ理論 を使用して行うことができます。特に、における頂点から頂点までの長さの閉経路の数は、行列の 番目の行と番目の列の要素であることに注意してください。ここで、は の隣接行列です。 ${\displaystyle \ell}$${\displaystyle i}$${\displaystyle j}$${\displaystyle G}$${\displaystyle i}$${\displaystyle j}$${\displaystyle A^{\ell}}$${\displaystyle A}$${\displaystyle G}$

の 2 つの頂点とを固定することにより、反対側の端にと を持つの各コピーは、との 2 つの(必ずしも異なるとは限らない) 共通近傍を選択することによって識別できます。を との符号次数(つまり共通近傍の数) とすると、次のようになります。 ${\displaystyle u}$${\displaystyle v}$${\displaystyle G}$${\displaystyle C_{4}}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle \operatorname {codeg} (u,v)}$${\displaystyle u}$${\displaystyle v}$

${\displaystyle \operatorname {hom} (C_{4},G)=\sum _{u,v\in V(G)}\operatorname {codeg} (u,v)^{2}\geq {\frac {1}{n^{2}}}\left(\sum _{u,v\in V(G)}\operatorname {codeg} (u,v)\right)^{2}}$

コーシー・シュワルツの不等式によって、合計はすべての頂点のペアとその共通の隣接点の数になり、これはすべての頂点とその隣接点のペアの数と同じになります。つまり、

${\displaystyle \operatorname {hom} (C_{4},G)\geq {\frac {1}{n^{2}}}\left(\sum _{x\in V(G)}\deg(x)^{2}\right)^{2}\geq {\frac {1}{n^{2}}}\left({\frac {1}{n}}\left(\sum _{x\in V(G)}\deg(x)\right)^{2}\right)^{2}={\frac {1}{n^{2}}}\left({\frac {1}{n}}(n\cdot pn)^{2}\right)^{2}=p^{4}n^{4}}$

再びコーシー＝シュワルツによる。つまり：

${\displaystyle t(C_{4},G)={\frac {\operatorname {hom} (C_{4},G)}{n^{4}}}\geq p^{4}}$

ご希望に応じて。

に対するコーシー・シュワルツのアプローチは簡潔かつ初歩的ですが、すべての偶数サイクルにすぐに一般化できるわけではありません。ただし、スペクトルグラフ理論を適用すれば、すべての偶数サイクルがシドレンコの性質を持つことを証明できます。奇数サイクルは二部ではないため、シドレンコの予想では考慮されないことに注意してください。 ${\displaystyle C_{4}}$

閉じた経路についての観察を用いると、 は の対角要素の合計であることがわかります。これはのトレースに等しく、トレースはの固有値の 番目の累乗の合計に等しくなります。が の固有値である場合、最小最大定理は次のことを意味します。 ${\displaystyle \operatorname {hom} (C_{2k},G)}$${\displaystyle A^{2k}}$${\displaystyle A^{2k}}$${\displaystyle 2k}$${\displaystyle A}$${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \dots \geq \lambda _{n}}$${\displaystyle A}$

${\displaystyle \lambda _{1}\geq {\frac {\mathbf {1} ^{\intercal }A\mathbf {1} }{\mathbf {1} ^{\intercal }\mathbf {1} }} ={\frac {1}{n}}\sum _{x\in V(G)}\deg(x)=pn,}$

ここで、はすべての要素が であるベクトルです。しかし、次のようになります。 ${\displaystyle \mathbf {1} }$${\displaystyle n}$${\displaystyle 1}$

${\displaystyle \operatorname {hom} (C_{2k},G)=\sum _{i=1}^{n}\lambda _{i}^{2k}\geq \lambda _{1}^{2k }\geq p^{2k}n^{2k}}$

実対称行列の固有値は実数であるためです。したがって、

${\displaystyle t(C_{2k},G)={\frac {\operatorname {hom} (C_{2k},G)}{n^{2k}}}\geq p^{2k}}$

ご希望に応じて。

JL Xiang Li とBalázs Szegedy (2011) は、エントロピーを使用してシドレンコ予想のいくつかのケースを証明するというアイデアを紹介しました。Szegedy (2015) は後にこのアイデアをさらに応用して、さらに広いクラスの二部グラフがシドレンコの性質を持つことを証明しました。^[2] Szegedy の証明は抽象的で技術的なものになりましたが、Tim Gowersと Jason Long は、長さ のパスなどの特定のケースに対して議論をより単純なものに簡略化しました。^[3]本質的には、この証明では、パスの頂点を選択する適切な確率分布を選択し、 Jensen の不等式(つまり凸性) を適用して不等式を導き出します。 ${\displaystyle 3}$

以下は、シドレンコ特性を持つことが示されている二部グラフのリストです。 が二部グラフであるとします。 ${\displaystyle H}$${\displaystyle H}$${\displaystyle A\sqcup B}$

• パスにはシドレンコの性質があり、これは1959年にマルホランドとスミスによって示されました（シドレンコが予想を定式化する前）。^[4]
• 木にはシドレンコの性質があり、経路を一般化する。これはシドレンコが1991年の論文で示した。^[5]
• 偶数長さのサイクルには、前述のとおりシドレンコの特性があります。シドレンコは 1991 年の論文でもこれを実証しました。
• 完全二部グラフにはシドレンコの性質があります。これはシドレンコの 1991 年の論文でも示されました。
• 二部グラフにはシドレンコ特性があります。これはシドレンコの 1991 年の論文でも示されました。${\displaystyle \min\{|A|,|B|\}\leq 4}$
• ハイパーキューブグラフ（の一般化）はシドレンコの性質を持ち、これは2008年にハタミによって示された。^[6]${\displaystyle Q_{3}}$
  • より一般的には、Hatami によって導入されたノルムグラフには、Sidorenko の特性があります。
• 内の頂点が内の全ての頂点と隣接している場合（またはその逆）、 はシドレンコの性質を持ちます。これは2010年にConlon、Fox、Sudakovによって示されました。 ^{[7]この証明では}従属ランダム選択法が使用されました。${\displaystyle A}$${\displaystyle B}$${\displaystyle H}$
• すべての二部グラフ に対して、 の-ブローアップがシドレンコの性質を持つような正の整数が存在します。ここで、の -ブローアップは、内の各頂点を自身のコピーに置き換え、各コピーを 内の元の隣接頂点と接続することによって形成されます。これは 2018 年に Conlon と Lee によって示されました。^[8]${\displaystyle H}$${\displaystyle p}$${\displaystyle p}$${\displaystyle B}$${\displaystyle p}$${\displaystyle H}$${\displaystyle B}$${\displaystyle p}$${\displaystyle A}$
• シドレンコ特性を持つグラフの集合からシドレンコ特性を持つ新しいグラフを作成するという再帰的なアプローチもいくつか試みられてきた。この方法の主な進歩は、シドレンコの1991年の論文、LiとSzegedyの2011年論文^[9]、Kim、Lee、Leeの2013年論文^{[10]によって達成された。}
  • Li 氏と Szegedy 氏の論文では、エントロピー法を使用して、「反射木」と呼ばれるグラフのクラスの特性も証明しました。
  • Kim、Lee、Lee の論文では、この考え方を「ツリー配置可能グラ​​フ」と呼ばれるツリーのようなサブ構造を持つグラフのクラスに拡張しました。

しかし、シドレンコの予想がまだ未解決のグラフもあります。一例として、サイズ の部分を持つ完全な二部グラフから -サイクルを削除することによって形成される「メビウスの帯」グラフ があります。 ${\displaystyle K_{5,5}\setminus C_{10}}$${\displaystyle 10}$${\displaystyle 5}$

ラースロー・ロヴァースは、シドレンコ予想の局所版、すなわちカットノルムの意味でランダムグラフに「近い」グラフを証明した。^[11]

グラフのシーケンスは、任意のグラフに対して次の条件を満たす場合、ある密度に対して密度を持つ準ランダムと呼ばれます。 ${\displaystyle \{G_{n}\}_{n=1}^{\infty }}$${\displaystyle p}$${\displaystyle 0<p<1}$${\displaystyle H}$

${\displaystyle t(H,G_{n})=(1+o(1))p^{|E(H)|}.}$

したがって、グラフのシーケンスはエルデシュ・レーニランダムグラフ の特性を持つことになります。 ${\displaystyle G(n,p)}$

辺密度が に固定されている場合、条件は、グラフのシーケンスがすべてのグラフ に対してシドレンコの性質における等式ケースに近いことを意味します。 ${\displaystyle t(K_{2},G_{n})}$${\displaystyle (1+o(1))p}$${\displaystyle H}$

準ランダムグラフに関する Chung、Graham、Wilson の 1989 年の論文によれば、カウントがランダムグラフに期待されるものと一致すれば十分である (つまり、条件は に対して成り立つ)。^[12]この論文では、 以外にどのグラフがこの特性を持つかについても問われている。このようなグラフは、そのカウントがグラフのシーケンスの準ランダム性を制御するため、 強制グラフと呼ばれる。${\displaystyle C_{4}}$${\displaystyle H=C_{4}}$${\displaystyle H}$${\displaystyle C_{4}}$

強制予想は次のように述べます。

グラフが強制的であるためには、それが二部グラフであり、ツリーではない必要があります。${\displaystyle H}$

が強制グラフである場合、それは二部グラフであり木ではないことは簡単にわかります。強制グラフの例には、偶数サイクルがあります（Chung、Graham、Wilsonによって示されています）。SkokanとThomaは、木ではないすべての完全な二部グラフが強制グラフであることを示しました。^[13]${\displaystyle H}$

密度グラフに関するシドレンコ予想は強制予想から導かれる。さらに、強制予想は、シドレンコの性質において等式に近いグラフは準ランダム性条件を満たさなければならないことを示す。^[14]${\displaystyle p}$

• 共通グラフ