칸-칼라이 추측

기대 임계값 추측으로도 알려진 칸-칼라이 추측은 그래프 이론과 통계 역학 분야의 추측으로, 2006년 ^[1][2]제프 칸과 길 칼라이가 제안했다.

배경

이 추측은 시스템에서 ^[1]위상 천이가 언제 발생하는지를 추정하는 일반적인 문제와 관련이 있습니다.예를 들어$$N개의 $노드$를 가진 $랜덤네트워크$에서 각 에지가 $확률{\displaystyle }$ p$\displaystyle$ p$\}$에 포함되는 경우 p$\displaystyle$ p$}$가 임계값$({\displaystyle \log n}$N$)/$$\displaystyle(\log$ N$)/N$보다 작을 $경우{\displaystyle }$ $그래프$에 해밀턴 사이클이 포함될 가능성은 거의 없습니다.${\displaystyle }${\$displaystyle$ p$}$이(^[3]가) 임계값을 초과합니다$.$

임계값은 종종 계산하기 어렵지만 임계값의 하한인 "기대 임계값"은 일반적으로 ^[1]계산하기가 더 쉽습니다.Kahn-Kalai 추측은 두 값이 일반적으로 정확하게 정의된 방식으로 서로 가깝다는 것입니다. 즉, 두 값 사이의 비율이 ${\displaystyle K}$ ${\displaystyle \log }$ (${\displaystyle F\mathcal{}}$) \ $display style$ K$\$$log$ \$ell$ ( \$mathcal${$F$} ) )} ( \ mathcal { F${\displaystyle }$} ) $ℓ$ ${\displaystyle （}$ \ $mathc$$）$ 。al ${F}})$은 멱집합 ^[4]서브셋의 증가 $패밀리{\displaystyle \mathcal{}}$ F$(\$ 중 최소$$ 요소의 최대 크기입니다.

증명

2022년 박진영과 후이툰팜은 ^[3][4]이 추측의 증거를 담은 프리프린트를 공개했다.그 증거는 우아하고 ^[5]간결하다는 평을 받고 있다.

레퍼런스

「 」를 참조해 주세요.

• 침투 이론