Integral bases, perfect matchings, and the Petersen graph
Mathematical Programming · 30.07.2026
DOI: 10.1007/s10107-026-02401-w ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematical Programming, online erschienen am 30.07.2026. Verfasst von Ahmad Abdi und 1 weiteren Autor:innen. Die Arbeit nennt 19 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Engineering and Physical Sciences Research Council.
Abstract (Originalsprache)
Let $$G=(V,E)$$ 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 (a) L has a lattice basis consisting solely of incidence vectors of some perfect matchings of G , (b) $$2x\in L$$ 2 x ∈ L for all $$x\in {{\,\textrm{lin}\,}}(P)\cap \mathbb {Z}^E$$ x ∈ lin ( P ) ∩ Z E , and (c) if G has no Petersen brick then $$L = {{\,\textrm{lin}\,}}(P)\cap \mathbb {Z}^E$$ L = lin ( P ) ∩ 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.
Förderung
- Engineering and Physical Sciences Research Council
Zitieren
APA
Abdi, A., & Silina, O. (2026). Integral bases, perfect matchings, and the Petersen graph. Mathematical Programming. https://doi.org/10.1007/s10107-026-02401-w
Vancouver
Abdi A, Silina O. Integral bases, perfect matchings, and the Petersen graph. Mathematical Programming. 2026. doi:10.1007/s10107-026-02401-w
BibTeX
@article{Abdi2026,
author = {Abdi, Ahmad and Silina, Olha},
title = {Integral bases, perfect matchings, and the Petersen graph},
journal = {Mathematical Programming},
year = {2026},
doi = {10.1007/s10107-026-02401-w}
}
EUVIMED