Isomorphisms between dense random graphs
From MaRDI portal
Publication:6435804
arXiv2305.04850MaRDI QIDQ6435804FDOQ6435804
Authors: Lutz Warnke, Emily Zhu 
Publication date: 8 May 2023
Abstract: We consider two variants of the induced subgraph isomorphism problem for two independent binomial random graphs with constant edge-probabilities p_1,p_2. We resolve several open problems of Chatterjee and Diaconis, and also confirm simulation-based predictions of McCreesh, Prosser, Solnon and Trimble: (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 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 limiting distribution.
Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorial probability (60C05)
This page was built for publication: Isomorphisms between dense random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6435804)
