Mathematical Programming Программное обеспечение

Integral bases, perfect matchings, and the Petersen graph

Ahmad Abdi, Olha Silina
Springer Nature · 2026-07-30 · DOI 10.1007/s10107-026-02401-w

Аннотация

Abstract 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.

Читать у издателя →