ISOMORPHISMS BETWEEN RANDOM GRAPHS

Abstract: Pick two Erdős-Rényi G(n,1/2) graphs at random. What's the chance that they are isomorphic? Small right? How small? It's at most n!/2^(n choose 2) so less than 10^(-1300) when n= 100. That's small. OK, now let n= infinity. The chance that they are isomorphic is one(!). Thus we may talk about THE random graph R. I will review it's many strange properties and then ask if there is any finite shadow of this isomorphism. In joint work with Sourav Chatterjee we show that the largest isomorphic induced subgraph of two independent G(n,1/2) graphs is about 4 log n. Constraint satisfaction problems suggest related problems. There are some surprising results and many open problems.