Isomorphisms between random graphs

Abstract

Consider two independent Erdős-Rényi $G(N,1/2)$ graphs. We show that with probability tending to $1$ as $N\to \infty$, the largest induced isomorphic subgraph has size either $\lfloor x_N-{\epsilon }_N\rfloor$ or $\lfloor x_N+{\epsilon }_N\rfloor$, where $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}$. Using similar techniques, we also show that if $\hat{I}{“}_1$ and $\hat{I}{“}_2$ are independent $G(n,1/2)$ and $G(N,1/2)$ random graphs, then $\hat{I}{“}_2$ contains an isomorphic copy of $\hat{I}{“}_1$ as an induced subgraph with high probability if $n\le \lfloor y_N-{\epsilon }_N\rfloor$ and does not contain an isomorphic copy of $\hat{I}{“}_1$ as an induced subgraph with high probability if $n>\lfloor y_N+{\epsilon }_N\rfloor$, where $y_N=2{\log }_{2}N+1$ and ${\epsilon }_N$ is as above.

17 pages. To appear in J. Combin. Theory B