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
Adam Mickiewicz University
Technical University of Denmark, DTU