The Homotopy Types of the Independence and Perfect Matching Complexes of Möbius and Circular Ladder Graphs

Abstract

The independence complex and perfect matching complex of a graph are simplicial complexes encoding, respectively, its independent sets and perfect matchings. Determining their homotopy types is generally difficult, with explicit descriptions known mainly for highly structured graph families. In this article, we determine the homotopy types of these complexes for the Möbius ladder graphs $M_{2n}$ and circular ladder graphs ${\mathcal{C}}_{2n}$. The Möbius ladder graphs $M_{2n}$ are highly symmetric cubic graphs obtained from a $2n$-cycle by joining opposite vertices, while the circular ladder graphs ${\mathcal{C}}_{2n}$ are the Cartesian products of an $n$-cycle and a path of length one. We show that $\mathrm{Ind}(M_{2n})$ and $\mathrm{Ind}({\mathcal{C}}_{2n})$ have the homotopy type of wedges of spheres, with the numbers and dimensions of the spheres exhibiting periodic behavior according to $n$ modulo $4$. For the perfect matching complex ${\mathcal{M}}_p(M_{2n})$, its homotopy type is a wedge of two copies of ${\mathbb{S}}^{(n-2)/2}$ when $n$ is even, while for odd $n$ it has the homotopy type of a wedge of spheres whose numbers and dimensions depend periodically on $n$ modulo $6$. The perfect matching complex ${\mathcal{M}}_p({\mathcal{C}}_{2n})$ is contractible for odd $n$, whereas for even $n$ its homotopy type is a wedge of spheres, with the numbers and dimensions determined periodically by $n$ modulo $6$. Thus, we obtain explicit homotopy types for the independence and perfect matching complexes of two highly symmetric families of cubic graphs, which are also relevant in crystallization theory and the combinatorial representation of PL manifolds.

19 pages, 6 Figures