Georgia Institute of Technology College of Sciences

I’ll describe some recent work (joint with Jeff Kahn and Jinyoung Park) on the "Second" Kahn--Kalai Conjecture (KKC2), the original conjecture on graph containment in $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_{n,p}$, 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. Thus, according to KKC2, the simplest expectation considerations predict $p_c(H)$ up to a log factor. This serves as a refinement of PPT in the restricted case of graph containment in $G_{n,p}$. Our main result is that $p_c(H) < O(p_E(H) log^3(n))$. This last statement follows (via PPT) from our results on a completely deterministic graph theory problem about maximizing subgraph counts under sparsity constraints.