カーン・カライ予想

カーン・カライ予想（期待値閾値予想、あるいは最近ではパーク・ファム定理とも呼ばれる）は、グラフ理論と統計力学の分野における予想であり、 2006年にジェフ・カーンとギル・カライによって提唱された。^{[ 1 ] [ 2 ]}これは2024年に発表された論文で証明された。^{[ 3 ]}

この推測は、システムにおける相転移の発生時期を推定するという一般的な問題に関するものである。^{[ 1 ]}例えば、ランダムネットワークでは、${\displaystyle N}$ノード、各エッジは確率で含まれる${\displaystyle p}$グラフにハミルトン閉路が含まれる可能性は低い。${\displaystyle p}$しきい値より小さい${\displaystyle (\log N)/N}$しかし、可能性は非常に高い${\displaystyle p}$その閾値を超えている。^{[ 4 ]}

閾値の計算はしばしば困難ですが、閾値の下限値である「期待閾値」は一般的に計算しやすいです。^{[ 1 ]}カーン・カライ予想は、2つの値が一般的に厳密に定義された方法で近い値をとる、つまり普遍定数が存在するというものです。${\displaystyle K}$2つの比率が以下${\displaystyle K\log {l({\mathcal {F}})}}$どこ${\displaystyle l({\mathcal {F}})}$増加族の最大最小要素のサイズ$\displaystyle {\mathcal {F}}}$冪集合の部分集合。^{[ 3 ]}

ジニョン・パクとフイ・トゥアン・ファムは2022年に予想の証明を発表し、2024年に出版された。^{[ 4 ] [ 3 ]}

• 浸透理論