Séminaire MODAL'X : Mike Liu (Institut Polytechnique de Paris)

Abstract: Look at an Erdös-Renyi Graph with independent edge weights, if the weights are atomless, the maximum weight matching is uniquely defined. We study the asymptotic geometric behavior of this optimum, in particular, we show that the optimum matching, seen as a geometric graph, converges locally to a matching on the limiting object of the graph called the unimodular Bienaymé Galton Watson tree. 
We also show, when the weights are atomic, the convergence of the tiebreaked maximum weight matching.
This convergence generalizes to a larger class of optimization problems on sparse configuration graphs.
This work is a continuation of the objective method introduced by D. Aldous in 2000 and is based on two papers coming out soon done with my PhD advisors Laurent Ménard, Nathanaël Enriquez and Vianney Perchet.