Joel Larsson: Minimum matching, replica symmetry, and exploration games

For the complete bipartite graph on n+n vertices with edge costs given by independent exp(1)-variables, Parisi conjectured that the cost of the minimum matching converges to p²/6 in probability as n goes to infinity. This was later proven by Aldous, and similar results have been established for other random graph models.

By studying exploration games, Wästlund established convergence for graph models of pseudo-dimension d = 1. (A random graph model is said to be of pseudo-dimension d if the edge costs are i.i.d. and have density function of order x^(d-1) near 0.) In this talk, I will extend Wästlund's result to pseudo-dimension d > 0.