Add to Outlook calendar Add to Google calendar

APRG Seminar

Title: Isomorphisms between dense random graphs
Speaker: Lutz Warnke (University of California, San Diego, USA)
Date: 04 July 2024
Time: 11:15 am
Venue: LH-1, Mathematics Department

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 an unusual ‘squashed lognormal’ limiting distribution.

These results resolve several open problems of Chatterjee and Diaconis, and confirm simulation-based predictions of McCreesh, Prosser, Solnon and Trimble. The proofs are based on careful refinements of the first and second moment method, using extra twists to (a) take some non-standard behaviors 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 my PhD students Erlang Surya and Emily Zhu; see arXiv:2305.04850.


Contact: +91 (80) 2293 2711, +91 (80) 2293 2265 ;     E-mail: chair.math[at]iisc[dot]ac[dot]in
Last updated: 15 Jul 2024