Isomorphisms between dense random graphs
The main goal of this paper concerns a fundamental problem of graph theory: to determine whether an induced copy of a graph \(F\) (or a large part of \(F\)) is contained in another graph \(G\). The authors consider two probabilistic variants of this problem, where the graphs \(F\) and \(G\) are both independent binomial random graphs with constant edge-probabilities \(p_1,p_2\in (0,1)\).\par From the authors' abstract: ``In particular, (i) we prove a sharp threshod 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 limiting distribution.\N\NThese results confirm simulation-based predictions of \textit{C. McCreesh} et al. [J. Artif. Intell. Res. (JAIR) 61, 723--759 (2018; Zbl 1440.68192)], and resolve several open problems of \textit{S. Chatterjee} and \textit{P. Diaconis} [J. Comb. Theory, Ser. B 160, 144--162 (2023; Zbl 1511.05208)]. 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.
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 Q6952666)
