Matching structure and the matching lattice (Q1112071): Difference between revisions

Let G be a graph and let M denote the set of its perfect matchings. It is natural to consider M as a set of 0-1 vectors indexed by edges of G and to take various hulls of M in the resulting linear space. The convex hull was characterized by \textit{J. Edmonds} [J. Res. Nat. Bur. Standards B69, 125-130 (1965; Zbl 0141.218)]; this result is the key to a large part of polyhedral combinatorics. The linear hull was characterized by \textit{D. Naddef} [Math. Program. 22, 52-70 (1982; Zbl 0468.90052)]. The main result of this paper is the description of the lattice generated by M, i.e., the set of all integer linear combinations of elements of M. The decomposition of G into bricks is used and the role of the Petersen graph is revealed.