Large Structures Seminar: Joel Larsson

Let G be the complete bipartite graph on n+n vertices, and equipped with i.i.d. edge costs, drawn from some distribution with cdf $F$. Let $M$ be the cost of the minimum matching on G. The Mézard-Parisi Conjecture (85) states that if there is a q>0 such that $F(t) ~ t^q$ for small t, then $Mn^{-1+1/q}$ converges in probability to a constant (implicitly given as the solution to a certain equation) as n goes to infinity. The conjecture has been established for q=1 (Aldous 01), where the constant is $\pi^2/6$, and q>1 (Wästlund 12). We extend those results to all q>0, thus establishing the conjecture in the last applicable cases.

This seminar takes place together with Aalto Stochastics Seminar.