グラフ理論において、フォーシンググラフとは、グラフ列が擬似ランダムであるかどうかをその密度によって決定するグラフのことである。この用語は、1989年にChung、Graham、Wilsonによって初めて造語された。[1]フォーシンググラフは、グラフ列における擬似ランダム性の研究において重要な役割を果たしている。
フォーシング予想は、フォーシンググラフがまさに巡回二部グラフであるという予想である。これは「極限組合せ論における主要な未解決問題の一つ」とされている。[2]
定義
t ( H , G ) = G内のHのラベル付きコピー数/v ( G ) v ( H ) 、サブグラフ密度として知られる(特に、 t ( K 2、G )はGのエッジ密度である)。グラフのシーケンス{ G n }が準ランダムと呼ばれるのは、すべてのグラフHについて、エッジ密度t ( K 2、G n )が何らかのpに近づき、 t ( H、G n )がp e(H)に近づく場合である。ここで、 e ( H )はHのエッジの数である。直感的には、これは、特定のエッジ密度を持つグラフシーケンスには、ランダムグラフシーケンスで期待されるグラフ準同型の数があることを意味します。グラフFは、 t ( K 2、G n )がnが無限大になるにつれてpに近づくすべてのグラフシーケンス{ G n }について、 t ( F、G n )がp e ( F )に近づく場合、 { G n }が準ランダムであるとき、強制グラフと呼ばれます。言い換えれば、単一のグラフの準同型密度を調べるだけで、グラフのシーケンスが準ランダムであることを検証できる。 [3]
グラフオンの言語を用いた強制グラフの2つ目の定義があります。正式には、 t ( F , W ) = t ( K 2 , W ) e ( F )を満たすすべてのグラフオンWが定数である場合、グラフは強制グラフと呼ばれます。直感的に、これらの定義が関連していることは理にかなっています。定数グラフオンW ( x , y ) = pはエルデシュ・レーニイランダムグラフG ( n , p )を表すため、準ランダムグラフと密接な関係があると予想されます。実際、これらの定義は同等です。[要出典]
例
最初に検討すべき強制グラフは4サイクルC 4である。これは、他の準ランダム性条件と密接な関係があるからである。Chung、Graham、Wilsonは同じ論文で、すべての偶数サイクルC 2 tと、 t ≥ 2のK 2, tの完全二部グラフが強制グラフであることを示した。[1] Conlon、Fox、Sudakovはこの最後の結果を拡張し、一方の部分に2つの頂点があり、もう一方の部分にも完全であるすべての二部グラフを含むようにした[3]。
家族を強制する
強制族は強制グラフの自然な一般化を提供する。グラフ族Fが強制{ G n }であるとき、任意のF ∈ Fに対してt ( F , G n )がp e ( F )に近づくとき、グラフ族 Fは準ランダムとなる。強制族を特徴づけることは強制グラフを特徴づけることよりもはるかに困難であるため、知られている強制族は少ない。既知の強制族には以下のものがある。
- { K 2 , C 2 t }(tは正の整数)
- { C 2 s、C 2 t }、ここでsとtはs ≠ tとなる正の整数である。
- { K 2 , K 2, t } , ただしt ≥ 2 ; および
- { K 2, s , K 2, t } , ただしs ≠ tかつs , t ≥ 2。[1]
推測を強制する
強制予想は2004年にスコカンとトーマによって提唱され[4]、2010年にコンロン、フォックス、スダコフによって形式化されました[3]。これは強制グラフの特徴付けを提供し、次のように形式化されます。
グラフが強制的となるのは、それが二部グラフであり、サイクルが含まれている場合のみです。
この主張の一方向はよく知られている。Chung、Graham、Wilsonは、グラフが奇数サイクルを持つ場合、それは強制グラフではないことを示した[1]。したがって、グラフが強制グラフである場合、それは二部グラフでなければならない。また、Conlon、Fox、Sudakovは、{ G n }がほぼ規則的な(必ずしも準ランダムではない)グラフシーケンスである場合、すべてのフォレストHについてt ( H , G n )がp e ( H )に近づくと主張した[3] 。したがって、強制グラフは二部グラフであり、少なくとも1つのサイクルを持つ必要がある。もう一方の方向はまだ証明されていないが、これらの特性の両方を持たない強制グラフは見つかっていない。
フォーシング予想は、この分野で長年提唱されているシドレンコ予想も含意する。すべてのフォーシンググラフはシドレンコグラフであることが知られているため、フォーシング予想が正しいとすれば、少なくとも1つのサイクルを持つすべての二部グラフはシドレンコグラフとなる。 [3]木はシドレンコグラフであるため、[5]すべての二部グラフはシドレンコグラフとなる。
参考文献
- ^ abcd Chung, FRK; Graham, RL; Wilson, RM (1989-12-01). 「準ランダムグラフ」 . Combinatorica . 9 (4): 345– 362. doi :10.1007/BF02125347. ISSN 1439-6912. S2CID 17166765.
- ^ Hancock, Robert; Kabela, Adam; Král', Daniel; Martins, Taísa; Parente, Roberto; Skerman, Fiona; Volec, Jan (2023). 「追加トーナメントは準ランダム強制ではない」. European Journal of Combinatorics . 108 103632: Paper No. 103632, 10. arXiv : 1912.04243 . doi :10.1016/j.ejc.2022.103632. MR 4502205.
- ^ abcde Conlon, David; Fox, Jacob; Sudakov, Benny (2010-10-20). 「シドレンコ予想の近似版」. Geometric and Functional Analysis . 20 (6): 1354– 1366. arXiv : 1004.4236 . doi :10.1007/s00039-010-0097-0. ISSN 1016-443X. S2CID 1872674.
- ^ Skokan, Jozef; Thoma, Lubos (2004-06-01). 「二部サブグラフと準ランダム性」.グラフと組合せ論. 20 (2): 255– 262. doi :10.1007/s00373-004-0556-1. ISSN 0911-0119. S2CID 2154492.
- ^ SIDORENKO, AF (1992). 「二部グラフによって生成される関数の不等式」 .離散数学とその応用. 2 (5). doi :10.1515/dma.1992.2.5.489. ISSN 0924-9265. S2CID 117471984.