Applied benchmark tests for the famous `subgraph isomorphism problem' empirically discovered interesting phase transitions in random graphs. This motivates our rigorous study of two variants of the induced subgraph isomorphism problem for two independent binomial random graphs with constant edge-probabilities p_1,p_2. In particular, (i) we prove a sharp threshold result for the appearance of G_{n,p_1} as an induced subgraph of G_{N,p_2}, (ii) we show two-point concentration of the size of the maximum common induced subgraph of G_{N, p_1} and G_{N,p_2}, and (iii) we show that the number of induced copies of G_{n,p_1} in G_{N,p_2} has a `squashed lognormal' limiting distribution. These results confirm simulation-based phase transition predictions of McCreesh-Prosser-Solnon-Trimble, and resolve several open problems of Chatterjee-Diaconis.

The proofs are based on careful refinements of the first and second moment method, using several extra twists to (a) take the non-standard behavior into account, and (b) work around the large variance issues that prevent standard applications of the second moment method, using in particular pseudorandom properties and multi-round exposure arguments to tame the variance.

Based on joint work with Erlang Surya and Emily Zhu (both UCSD).