James Martin

Matchings, games, and cores in random graphs

I will survey various older and newer results about phase transitions on trees, cores of random graphs, and random matchings.

For suitable families of configuration models, the emergence of a giant component, or of a giant 3-core, can be related to phase transitions for Bienayme-Galton-Watson trees. Similar correspondences relate the outcome of certain 2-player games played on BGW trees to the “Karp-Sipser” core (which appears naturally in the context of algorithms for finding large matchings of a graph).

I’ll mention various results which have been obtained recently on the size of the Karp-Sipser core, and on the maximum-size matching, for the Erdos-Renyi random graph in various regimes.

Finally I’ll describe how Stein coupling techniques developed by Barbour and Röllin can be extended to give CLTs for the size of the largest matching, and for other related statistics, in configuration models with suitable degree sequences.