Résumé : The "Minimum Matching Problem" consists in finding an independent edge set of minimum weight M*(G) in a given edge-weighted undirected graph G. If G is bipartite, we deal with the "Assignment Problem". We consider a version of the problem in which we take the union of the optimal matchings for various slightly-modified versions of the base graph: H_J(G)=Union_{U in J} M*(G_U). In this talk we will provide two families of theorems: (1) we prove that, in two distinct settings for the Assignment Problem, the graphs H_J, as well as certain associated graphs H'_J, are in fact spanning trees on the pertinent base graphs G and G'; (2) in the two settings above, if the weights of the graph edges are given by the p-th power of the Euclidean distance for points configurations on the plane, the tree H_J is non-crossing (that is, its natural embedding in the plane has no crossing edges) when p=1, and (more surprisingly) the associated tree H'_J is non-crossing when p=2. Our main motivation for investigating theorems of this form comes from (a family of) conjectures in Statistical Mechanics, that we will illustrate in future work: in the Random Euclidean Assignment Problem (i.e., when the points are chosen i.i.d. on a domain of the plane), for p=2, the two settings above give trees H'_J which are asymptotically distributed as the Uniform Spanning Tree with free and wired boundary conditions, in the two cases. In particular, suitable paths on the tree in the second setting are asymptotically distributed as a SLE at kappa=2. Work in collaboration with Sergio Caracciolo and Gabriele Sicuro

Dernière modification : Thursday 23 October 2025

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr