Leray numbers of complexes of graphs with bounded matching number

Abstract

Given a graph $G$ on the vertex set $V$, the non-matching complex of $G$, ${\mathsf{NM}}_k(G)$, is the family of subgraphs $G^{\prime }\subset G$ whose matching number $\nu (G^{\prime })$ is strictly less than $k$. As an attempt to generalize the result by Linusson, Shareshian and Welker on the homotopy types of ${\mathsf{NM}}_k(K_n)$ and ${\mathsf{NM}}_k(K_{r,s})$ to arbitrary graphs $G$, we show that (i) ${\mathsf{NM}}_k(G)$ is $(3k-3)$-Leray, and (ii) if $G$ is bipartite, then ${\mathsf{NM}}_k(G)$ is $(2k-2)$-Leray. This result is obtained by analyzing the homology of the links of non-empty faces of the complex ${\mathsf{NM}}_k(G)$, which vanishes in all dimensions $d\ge 3k-4$, and all dimensions $d\ge 2k-3$ when $G$ is bipartite. As a corollary, we have the following rainbow matching theorem which generalizes the result by Aharoni, Berger, Chudnovsky, Howard and Seymour: Let $E_1,\dots ,E_{3k-2}$ be non-empty edge subsets of a graph and suppose that $\nu (E_i\cup E_j)\ge k$ for every $i\ne j$. Then $E=\bigcup E_i$ has a rainbow matching of size $k$. Furthermore, the number of edge sets $E_i$ can be reduced to $2k-1$ when $E$ is the edge set of a bipartite graph.