A Polyhedral Perspective on the Perfect Matching Lattice
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915601698521088 |
|---|---|
| author | Silina, Olha |
| author_facet | Silina, Olha |
| contents | We study the perfect matching lattice of a matching covered graph $G$, generated by the incidence vectors of its perfect matchings. Building on results of Lovász and de Carvalho, Lucchesi, and Murty, we give a polynomial-time algorithm based on polyhedral methods that constructs a lattice basis for this lattice consisting of perfect matchings of $G$. By decomposing along certain odd cuts, we reduce the graph into subgraphs whose perfect matching polytopes coincide with their bipartite relaxations (known as \emph{Birkhoff von Neumann graphs}). This yields a constructive polyhedral proof of the existence of such bases and highlights new connections between combinatorial and geometric properties of perfect matchings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_03863 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Polyhedral Perspective on the Perfect Matching Lattice Silina, Olha Combinatorics 05C70, 90C27 G.2.2; G.2.1 We study the perfect matching lattice of a matching covered graph $G$, generated by the incidence vectors of its perfect matchings. Building on results of Lovász and de Carvalho, Lucchesi, and Murty, we give a polynomial-time algorithm based on polyhedral methods that constructs a lattice basis for this lattice consisting of perfect matchings of $G$. By decomposing along certain odd cuts, we reduce the graph into subgraphs whose perfect matching polytopes coincide with their bipartite relaxations (known as \emph{Birkhoff von Neumann graphs}). This yields a constructive polyhedral proof of the existence of such bases and highlights new connections between combinatorial and geometric properties of perfect matchings. |
| title | A Polyhedral Perspective on the Perfect Matching Lattice |
| topic | Combinatorics 05C70, 90C27 G.2.2; G.2.1 |
| url | https://arxiv.org/abs/2511.03863 |