Integral bases, perfect matchings, and the Petersen graph
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909026211594240 |
|---|---|
| author | Abdi, Ahmad Silina, Olha |
| author_facet | Abdi, Ahmad Silina, Olha |
| contents | Let $G=(V,E)$ be a matching-covered graph, denote by $P$ its perfect matching polytope, and by $L$ the integer lattice generated by the integral points in $P$. In this paper, we give short, polyhedral proofs for two difficult results established by Lovász (1987), and by Carvalho, Lucchesi, and Murty (2002) in a series of three papers totaling over 120 pages. More specifically, we prove that $L$ has a lattice basis consisting solely of incidence vectors of some perfect matchings of $G$, $2x\in L$ for all $x\in \mathrm{lin}(P)\cap \mathbb{Z}^E$, and if $G$ has no Petersen brick then $L = \mathrm{lin}(P)\cap \mathbb{Z}^E$. Our proof avoids major technical aspects of the previous proofs, the most important of these being a characterization of the dual lattice, and a `Petersen-brick-sensitive' ear decomposition result for matching-covered graphs. This is achieved by a novel study of the facial structure of the polytope $P$ and its relationship with the lattice $L$. It is also based on a first-of-its-kind polyhedral characterization of the Petersen graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_15602 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Integral bases, perfect matchings, and the Petersen graph Abdi, Ahmad Silina, Olha Combinatorics Optimization and Control 05Cxx, 52Bxx, 90C27, 90C10 Let $G=(V,E)$ be a matching-covered graph, denote by $P$ its perfect matching polytope, and by $L$ the integer lattice generated by the integral points in $P$. In this paper, we give short, polyhedral proofs for two difficult results established by Lovász (1987), and by Carvalho, Lucchesi, and Murty (2002) in a series of three papers totaling over 120 pages. More specifically, we prove that $L$ has a lattice basis consisting solely of incidence vectors of some perfect matchings of $G$, $2x\in L$ for all $x\in \mathrm{lin}(P)\cap \mathbb{Z}^E$, and if $G$ has no Petersen brick then $L = \mathrm{lin}(P)\cap \mathbb{Z}^E$. Our proof avoids major technical aspects of the previous proofs, the most important of these being a characterization of the dual lattice, and a `Petersen-brick-sensitive' ear decomposition result for matching-covered graphs. This is achieved by a novel study of the facial structure of the polytope $P$ and its relationship with the lattice $L$. It is also based on a first-of-its-kind polyhedral characterization of the Petersen graph. |
| title | Integral bases, perfect matchings, and the Petersen graph |
| topic | Combinatorics Optimization and Control 05Cxx, 52Bxx, 90C27, 90C10 |
| url | https://arxiv.org/abs/2508.15602 |