Hipoteza Kahna-Kalaia

Hipoteza Kahna-Kalai , znana również jako hipoteza progu oczekiwań , jest hipotezą z dziedziny teorii grafów i mechaniki statystycznej , zaproponowaną przez Jeffa Kahna i Gila Kalai w 2006 roku.

Tło

Przypuszczenie to dotyczy ogólnego problemu szacowania, kiedy w układach zachodzą przemiany fazowe . Na przykład w losowej sieci z $jeśli$ , w której każda krawędź jest zawarta z prawdopodobieństwem $displaystyle$ mało prawdopodobne, aby wykres zawierał cykl Hamiltona, p $p}$ niż wartość progowa ${\ Displaystyle (\ log N) / N}$ , ale bardzo prawdopodobne, jeśli ${\ displaystyle p}$ przekracza ten próg.

Wartości progowe są często trudne do obliczenia, ale dolna granica progu, „próg oczekiwań”, jest na ogół łatwiejsza do obliczenia. Hipoteza Kahna-Kalai polega $)$${\ Displaystyle K \ log \ ell ({\ mathcal {F}})}$ istnieje uniwersalna stała , dla której stosunek między nimi jest mniejszy niż gdzie $podzbiorów$$}})}$ to rozmiar największego minimalnego elementu rosnącej rodziny zbioru potęg.

Dowód

W 2022 roku Jinyoung Park i Huy Tuan Pham wydali przedruk zawierający proponowany dowód hipotezy. Dowód został doceniony za elegancję i zwięzłość.

Zobacz też

• Teoria perkolacji