Physics (Internal)

The Planted Matching Problem

What happens when an optimization problem has a good solution built into it, but which is partly obscured by randomness? Here we revisit a classic problem, the minimum perfect matching problem on bipartite graphs. If the edges have random weights in [0,1], Mézard and Parisi used the cavity method of spin glass theory to predict that the minimum matching has expected weight zeta(2) = pi^2/6, and Aldous then proved this using the framework of local weak convergence. We consider a planted model where a particular matching has weights drawn from an exponential distribution with mean mu. We show (rigorously) that there is a phase transition at mu=1/4 between perfect and partial recovery of the planted matching: when mu <= 1/4, the minimum matching is almost identical to the planted one, and when mu > 1/4, the overlap between the two is given by a system of differential equations that result from a message-passing algorithm. This is joint work with Mehrdad Moharrami (Michigan) and Jiaming Xu (Duke).