2025/11/05 by Olha Silina, Silina, Olha
Computer Science · Mathematics · #05C70 #90C27 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #G.2.1 #G.2.2 #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2511.03863
openalex publication_date 2025/11/05 · openalex created_date 2025/11/08 · openalex updated_date 2026/07/28
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 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.