A combinatorial approach to phase transitions in random graph isomorphism problems

Dimitris Diamantidis, Takis Konstantopoulos, Linglong Yuan

We consider two independent Erdős-Rényi random graphs, with possibly different parameters, and study two isomorphism problems, a graph embedding problem and a common subgraph probl…