657188news16497738981649774281<![CDATA[External News: Incoming Faculty Jinyoung Park Proves the Kahn-Kalai Expectation Threshold Conjecture]]>
Jinyoung Park, an incoming faculty member for Fall 2023, together with her coauthor Huy Tuan Pham have proven the Expectation Threshold Conjecture of Kahn and Kalai from 2006.

For the full article please click here, an excerpt is below.

The 2006 expectation threshold conjecture gives a justification for a naive way to estimate the threshold probability of a random graph property. Suppose that you are asked about the critical probability for a random graph in G(n,p) for having a perfect matching (or a Hamiltonian cycle). You compute the expected number of perfect matchings and realize that when p is C/n this expected number equals 1/2. (For Hamiltonian cycles it will be C’/n.) Of course, if the expectation is one half, the probability for a perfect matching can still be very low; indeed, in this case, an isolated vertex is quite likely but when there is no isolated vertices the expected number of perfect matchings is rather large. Our 2006 conjecture boldly asserts that the gap between the value given by such a naive computation and the true threshold value is at most logarithmic in the number of vertices. Jeff and I tried hard to find a counterexample but instead we managed to find more general and stronger forms of the conjecture that we could not disprove.

]]>
2022-04-12T00:00:00-04:00Jinyoung Park, an incoming faculty member for Fall 2023, has proven the the Kahn-Kalai Expectation Threshold Conjecture with coauthor Huy Tuan Pham.
]]>657187image<![CDATA[Jinyoung Park]]>249079image/jpegSal Barone
]]>1279https://gilkalai.wordpress.com/2022/04/02/amazing-jinyoung-park-and-huy-tuan-pham-settled-the-expectation-threshold-conjecture/?fbclid=IwAR3Wt4_73iRwFAyMx6zL7MCnMYfYheZJWk8318r766OR7VDu-d_jR3FayNYhttps://sites.google.com/view/jinyoungpark1279173647