Matching complexes of trees and applications of the matching tree algorithm.
A matching complex of a simple graph $G$ is a simplicial complex with faces given by the matchings on $G$. The topology of matching complexes is mysterious; there are few graphs for which the homotopy type is known. Marietti and Testa showed that matching complexes of forests are contractible or homotopy equivalent to a wedge of spheres. For a specific family of trees known as caterpillar graphs, we give explicit formulas for the number of spheres in each dimension. In cases where the homotopy type is more difficult to determine, a tool from discrete Morse theory called the Matching Tree Algorithm can be used to give bounds on the rank of non-trivial homology groups. In particular, we use the Matching Tree Algorithm to study the connectivity of honeycomb graphs, partially answering a question raised by Jonsson.