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.
Jinyoung Park is a Szegö Assistant Professor at Stanford University, working with her mentor Jacob Fox. Previously a postdoctoral member of Institute for Advanced Study (CSDM program, led by Avi Wigderson), Dr. Park will be joining SoM as an incoming faculty member in 2023.
Dr. Park's research interests include
extremal and probabilistic combinatorics,
asymptotic enumeration, and
graph theory.