  This work studies fundamental limits for recovering the underlying
correspondence among multiple correlated random graphs. We identify a necessary
condition for any algorithm to correctly match all nodes across all graphs, and
propose two algorithms for which the same condition is also sufficient. The
first algorithm employs global information to simultaneously match all the
graphs, whereas the second algorithm first partially matches the graphs
pairwise and then combines the partial matchings by transitivity. Both
algorithms work down to the information theoretic threshold. Our analysis
reveals a scenario where exact matching between two graphs alone is impossible,
but leveraging more than two graphs allows exact matching among all the graphs.
Along the way, we derive independent results about the k-core of Erdos-Renyi
graphs.
