• Séminaire / Formations,

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

Publié le 15 janvier 2024 Mis à jour le 15 janvier 2024

Optimal matching on sparse graphs through local analysis


le 18 janvier 2024

13h30 - 14h30

Bâtiment Maurice Allais (G)

Bâtiment Allais (G), salle Modal'X
Plan d'accès
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.

Mis à jour le 15 janvier 2024