Seminar

Zoom Link

I’ll describe some recent progress on the "Second" Kahn-Kalai Conjecture (KKC2), the original conjecture on graph containment in G = G_{n,p}  that motivated what is now the Park-Pham Theorem (PPT). KKC2 says that p_c(H), the threshold for containing a graph H in G, satisfies p_c(H) < O(p_E(H) log n), where p_E(H) is the smallest p such that the expected number of copies of any subgraph of H is at least one. In other words, for this class of problems, the expectation threshold q_f in PPT can be replaced by the smaller p_E. We show that q_f < O(p_E log^2(n)) (implying p_c(H) < O(p_E(H) log^3(n)) via PPT). This last statement will be formulated as a completely deterministic graph theory problem about maximizing subgraph counts under sparsity constraints. Joint with Jeff Kahn and Jinyoung Park.

The second Kahn-Kalai conjecture up to log factors