{"ID":2879882,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.15602","arxiv_id":"2508.15602","title":"Integral bases, perfect matchings, and the Petersen graph","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2508.15602","url_pdf":"https://arxiv.org/pdf/2508.15602v4","authors":"[\"Ahmad Abdi\",\"Olha Silina\"]","published":"2025-08-21T14:25:24Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"math.OC\"]","methods":"[]","has_code":false}