Isomorphisms between random graphs (Q2692783)

Consider two independent Erdős-Rényi random graphs \(G(N,1/2)\). What is the largest induced isomorphic subgraph of the two? (As usual, we work with high probability.) A naïve lower bound is the clique number of such graphs which is with high probability about \(2\log_{2}(N)\) (and known much more accurately). However the authors show that we can do better: the answer is in fact, letting \(x_{N}=4\log_{2}(N)-2\log_{2}\log_{2}(N)-2\log_{2}(4/e)+1\) and \(\epsilon_{N}=(4\log_{2}(N))^{-1/2}\), either \(\lfloor x_{N}-\epsilon_{N}\rfloor\) or \(\lfloor x_{N}+\epsilon_{N}\rfloor\) with high probability. The proof requires more than a usual second-moment estimate. It does not rule out the possibility that the answer might be concentrated on one value. The authors also consider the situation when \(\Gamma_{1}\) and \(\Gamma_{2}\) are independent \(G(n,1/2)\) and \(G(N,1/2)\), with \(n\) thought of as substantially smaller than \(N\). They show \(\Gamma_{2}\) has an induced subgraph which is an isomorphic copy of \(\Gamma_{1}\) with high probaility if \(n<y_{N}-\epsilon_{N}\) where \(y_{N}=2\log_{2}(N)+1\) and \(\epsilon_{N}\) is as above. However if \(n> y_{N}+\epsilon_{N}\), with high probability there is not an isomorphic copy of \(\Gamma_{1}\) as an induced subgraph. The proof techniques overlap with those in the first result.