A distributive lattice on the set of perfect matchings of a plane bipartite graph (Q1404376)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A distributive lattice on the set of perfect matchings of a plane bipartite graph |
scientific article |
Statements
A distributive lattice on the set of perfect matchings of a plane bipartite graph (English)
0 references
21 August 2003
0 references
Perfect matchings of (finite simple) graphs \(G\) have been widely studied over a (relatively) long time and the literature on this subject is considerable. Even so, interesting additions continue to be made as is quite clear from this paper where \(M(G)\), the set of perfect matchings, is provided a graph structure (edge means matchings differ by only one cycle that is the boundary of an inner face of \(G\)) whose acyclic orientation turns \(M(G)\) into a poset whose Hasse diagram is isomorphic to the \(Z\)-transformation graph and which is a distributive lattice via the elegant proof of the main theorem involving an embedding result employing certain combinatorial functions on the set of inner faces of \(G\), producing an important observation as a result.
0 references
distributive lattice
0 references
poset
0 references
perfect matching
0 references
Z-transformation graph
0 references
plane bipartite graph
0 references