2023/05/08 by Erlang Surya, Surya, Erlang, Lutz Warnke +3
Mathematics · #05C60 #05C80 #60C05 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2305.04850
openalex publication_date 2023/05/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We consider two variants of the induced subgraph isomorphism problem for two independent binomial random graphs with constant edge-probabilities p1,p2. In particular, (i) we prove a sharp threshold result for the appearance of Gn,p1 as an induced subgraph of GN,p2, (ii) we show two-point concentration of the size of the maximum common induced subgraph of GN, p1 and GN,p2, and (iii) we show that the number of induced copies of Gn,p1 in GN,p2 has an unusual limiting distribution. These results confirm simulation-based predictions of McCreesh, Prosser, Solnon and Trimble, and resolve several open problems of Chatterjee and Diaconis. 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 these methods.