Minimum matching, replica symmetry, and exploration games

Graphs, Hypergraphs, and Computing

08 April 15:30 - 16:30

Joel Larsson - Umeå University

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 π^2/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.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to