Higher matching complexes of complete graphs and complete bipartite graphs

Anurag Singh

Published 2020-06-24Version 1

For $r\geq 1$, the $r$-matching complex of a graph $G$, denoted $M_r(G)$, is a simplicial complex whose faces are the subsets $H \subseteq E(G)$ of the edge set of $G$ such that the degree of any vertex in the induced subgraph $G[H]$ is at most $r$. In this paper, we show that the complexes $M_{n-2}(K_n)$ and $M_{n-1}(K_{n,n})$ are homotopy equivalent to a wedge of spheres, where $K_n$ denotes the complete graph and $K_{m,n}$ denotes the complete bipartite graph. We also show that the complex $M_{r}(K_{m,n})$ is shellable whenever for $ m > r \geq n$. In each case, we give a closed form formula for their homotopy types.