A Polyhedral Perspective on the Perfect Matching Lattice
Olha Silina · 2025
Read A Polyhedral Perspective on the Perfect Matching Lattice by Olha Silina (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-03863.txt.
Introduction
Olha Silina, writing alone, studies the perfect matching lattice of a matching covered graph, the lattice generated by incidence vectors of all its perfect matchings. Building on work by Lovasz and by de Carvalho, Lucchesi, and Murty, Silina gives a polynomial-time, polyhedral method to build a lattice basis made of perfect matchings.
Decomposition along certain odd cuts reduces the graph to pieces whose perfect matching polytopes match their bipartite relaxations, known as Birkhoff-von Neumann graphs. That reduction yields a constructive proof that such bases exist. It also exposes fresh links between combinatorial structure and geometry in the theory of perfect matchings.
Catalog record
| CREATOR | Olha Silina |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-03863
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Polyhedral Perspective on the Perfect Matching Lattice Olha Silina Abstract We study the perfect matching lattice of a matching covered graph G 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 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. 1 Introduction Consider a graph G=(V,E) with an even number of vertices. A perfect matching is a set of edges M\subseteq E incident with each vertex exactly once. G is matching covered if every edge of G belongs to some perfect matching. The theory of matching covered graphs is a rich area of combinatorics with pioneering results due to Edmonds, Seymour, and Lovász. An object of particular interest is the perfect matching lattice , defined as the set of integral linear combinations of the incidence vectors of perfect matchings: \mathcal{L}(G):=\lat(\mathcal{M})=\{\sum_{M\in\mathcal{M}}k_{M}\mathbf{1}_{M}:k_{M}\in\mathbb{Z}\}, where \mathcal{M} denotes the set of all perfect matchings of G . Lovász [ 10 ] gave a characterization of this lattice based on a structural decomposition of the graph into blocks called bricks and braces , with the Petersen graph being the only obstruction for this lattice to contain all the integral points in the linear hull of the perfect matchings. A natural question is whether the generating set of this lattice, i.e. the perfect matchings of G , contains a basis for \mathcal{L}(G) . This question was answered positively by de Carvalho, Lucchesi, and Murty [ 4 ] who proved it through ear-decompositions of a graph. In this paper, we present an algorithmic analogue of this result, mainly: Theorem 1.1 . There is a polynomial time algorithm that, given a matching covered graph G , finds a lattice basis for \mathcal{L}(G) consisting of incidence vectors of perfect matchings of G . The main contribution of this paper is a new approach to basis construction for the perfect matching lattice based on polyhedral theory. In addition to the algorithmic result, we identify a class of graphs where a lattice basis can be obtained by a simple inductive process. Moreover, we connect the combinatorial and polyhedral properties of the perfect matchings, bridging our approach and structural methods of de Carvalho, Lucchesi, and Murty. More broadly, our polyhedral techniques offer new tools that may prove valuable in tackling longstanding open problems in matching theory. To begin with, the perfect matching polytope PM(G) is the convex hull of its perfect matching incidence vectors and is described by the following set of inequalities (Edmonds, [ 7 ] ): PM(G)=\left\{x\in\mathbb{R}^{A}_{+}:\begin{array}[]{cc}x(\delta(v))=1&\forall v\in V\\ x(C)\geq 1&\forall C\textmd{ odd cut}\end{array}\right\} (1) Here, a cut C=\delta(U) for some U\subseteq V is the set of edges with exactly one endpoint in U ; the sets U and its complement V\backslash U are the shores of C . A cut is odd if both of its shores have an odd cardinality. The main idea of the paper is to utilize odd cut decomposition methods to reduce our graph to a number of graphs whose perfect matching polytope coincides with its bipartite relaxation : P(G):=\left\{x\in\mathbb{R}^{A}_{+}:x(\delta(v))=1\forall v\in V\right\}. (2) Matching covered graphs for which PM(G)=P(G) are called Birkhoff von Neumann (BvN) graphs. All bipartite graphs and some non-bipartite graphs, in particular certain types of bricks (to be defined later) are BvN. Our algorithm for finding a basis for \mathcal{L}(G) either finds a set of \dim(P(G)) linearly independent integral vertices of P(G) or finds a facet of PM(G) induced by an odd cut constraint x(C)\geq 1 . We then use this facet to further decompose the graph into smaller ones until eventually the algorithm successfully finds a basis. The paper is organized as follows. In Section 2 we discuss a way to decompose the graph into simple pieces and show how to reduce the basis construction for \mathcal{L}(G) to these pieces. In Section 3 we describe a basis construction algorithm for Birkhoff von Neumann (BvN) graphs based on polyhedral techniques and discuss what happens when applying this algorithm to a non-BvN graph. In Section 4 we show how to decompose non-BvN graphs into BvN ones using a specific type of odd cuts in a process similar to the tight cut decomposition. In Section 5 we provide an algorithm to find an appropriate cut to be used in the above mentioned decomposition. Finally, in Appendix A.1 we draw connections between our polyhedral view of the basis and the classical approach based on ear decompositions . 2 Preliminaries 2.1 Tight cut decomposition Let G=(V,E) be a perfect matching covered graph. An odd cut C is tight if every perfect matching of G intersects it exactly once. Polyhedrally, these are the odd cuts whose corresponding constraint in ( 1 ) is an implicit equality. There are two types of odd cuts of particular interest. Definition 2.1 . A pair \{u,v\} of vertices in a matching covered graph G is a 2 -separation if G-u-v has at least two connected components of even cardinality. A set B\subseteq V of at least 2 vertices is a barrier if G-B has exactly |B| odd connected components. It is quite straightforward to see that if \{u,v\} is a 2 -separation in a matching covered G with U_{1} and U_{2} being the (even) components of G-u-v , then C:=\delta(U_{1}\cup\{u\}) and C^{\prime}:=\delta(U_{1}\cup\{v\}) are non-trivial tight cuts. We refer to these as 2 -separation cuts . Similarly, if B is a barrier with V_{1},V_{2},\ldots,V_{|B|} being odd components of G-B , then each of \delta(V_{i}) is a tight cut. We refer to these types of cuts as barrier cuts . The following result highlights the importance of the above definitions: Theorem 2.2 (Theorem 4.7 in [ 6 ] ) . If a perfect matching covered graph has a non-trivial tight cut then it has a barrier or 2 -separation tight cut. This theorem implies that tight cuts can be found efficiently. Indeed, it suffices to check for 2 -separation and barrier cuts. The former can be identified by going over all pairs of vertices \{u,v\} and counting the number of components in G-u-v . For barrier detection, we use the following characterization for maximal barriers, i.e. barriers that are not contained in larger barriers: Theorem 2.3 (Theorem 3.2 in [ 9 ] ) . The maximal barriers are exactly the equivalence classes under the equivalence relation on V : x\sim y iff G-x-y has no perfect matching. Once a tight cut is identified, one could contract it: for each of the two shores, consider a graph obtained by shrinking it into a single vertex. Thus, we obtain two smaller graphs. Repeating this process for the new set of graphs, we end up with a list of graphs obtained by contracting each shore of a tight cut into a single vertex. This process is known as tight cut decomposition and results in a