Optimal Unimodular Matching
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909555561070592 |
|---|---|
| author | Enriquez, Nathanaël Liu, Mike Ménard, Laurent Perchet, Vianney |
| author_facet | Enriquez, Nathanaël Liu, Mike Ménard, Laurent Perchet, Vianney |
| contents | We consider sequences of finite weighted random graphs that converge locally to unimodular i.i.d. weighted random trees. When the weights are atomless, we prove that the matchings of maximal weight converge locally to a matching on the limiting tree. For this purpose, we introduce and study unimodular matchings on weighted unimodular random trees as well as a notion of optimality for these objects. In this context, we prove that, in law, there is a unique optimal unimodular matching for a given unimodular tree. We then prove that this law is the local limit of the sequence of matchings of maximal weight. Along the way, we also show that this law is characterised by an equation derived from a message passing algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_03141 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimal Unimodular Matching Enriquez, Nathanaël Liu, Mike Ménard, Laurent Perchet, Vianney Probability Combinatorics 05C70, 05C82, 60C05, 60K35 We consider sequences of finite weighted random graphs that converge locally to unimodular i.i.d. weighted random trees. When the weights are atomless, we prove that the matchings of maximal weight converge locally to a matching on the limiting tree. For this purpose, we introduce and study unimodular matchings on weighted unimodular random trees as well as a notion of optimality for these objects. In this context, we prove that, in law, there is a unique optimal unimodular matching for a given unimodular tree. We then prove that this law is the local limit of the sequence of matchings of maximal weight. Along the way, we also show that this law is characterised by an equation derived from a message passing algorithm. |
| title | Optimal Unimodular Matching |
| topic | Probability Combinatorics 05C70, 05C82, 60C05, 60K35 |
| url | https://arxiv.org/abs/2407.03141 |