Kahn-Kalais gissningar

Kahn –Kalai-förmodan , även känd som förväntningströskelförmodan , är en gissning inom området grafteori och statistisk mekanik , föreslagen av Jeff Kahn och Gil Kalai 2006.

Bakgrund

Denna gissning gäller det allmänna problemet med att uppskatta när fasövergångar inträffar i system. Till exempel, i ett slumpmässigt nätverk med $N$ -noder, där varje kant ingår med sannolikheten $p$ , är det osannolikt att grafen innehåller en Hamiltonsk cykel om $p$ är mindre än ett tröskelvärde ${\displaystyle (\log N)/N} ,$ men mycket troligt om $p$ överskrider det tröskelvärdet.

Tröskelvärden är ofta svåra att beräkna, men en nedre gräns för tröskeln, "förväntningströskeln", är i allmänhet lättare att beräkna. Kahn–Kalais gissning är att de två värdena i allmänhet ligger nära varandra på ett exakt definierat sätt, nämligen att det finns en universell konstant $K$ för vilken förhållandet mellan de två är mindre än $K\log \ell ({\mathcal {F}})$ där $\ell ({\mathcal {F}})$ är storleken på det största minimala elementet i en växande familj ${\mathcal {F}}$ av delmängder av en effektmängd.

Bevis

År 2022 släppte Jinyoung Park och Huy Tuan Pham ett förtryck som innehöll ett föreslaget bevis på gissningarna. Beviset har prisats för sin elegans och koncisthet.

Se även

• Perkolationsteori