Perfect Matching Complexes of Honeycomb Graphs

Abstract

The {\em perfect matching complex} of a graph is the simplicial complex on the edge set of the graph with facets corresponding to perfect matchings of the graph. This paper studies the perfect matching complexes, ${\mathcal{M}}_p(H_{k\times m\times n})$, of honeycomb graphs. For $k=1$, ${\mathcal{M}}_p(H_{1\times m\times n})$ is contractible unless $n\ge m=2$, in which case it is homotopy equivalent to the $(n-1)$-sphere. Also, ${\mathcal{M}}_p(H_{2\times 2\times 2})$ is homotopy equivalent to the wedge of two 3-spheres. The proofs use discrete Morse theory.

28 pages