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, denoted by NMk(G), is the family of subgraphs G' & SUB; G whose matching number nu(G') is strictly less than k. As an attempt to extend the result by Linusson, Shareshian and Welker on the homotopy types of NMk(Kn) and NMk(Kr,s) to arbitrary graphs G, we show that (i) NMk(G) is (3k - 3)-Leray, and (ii) if G is bipartite, then NMk(G) is (2k-2)-Leray. This result is obtained by analyzing the homology of the links of non-empty faces of the complex NMk(G), which vanishes in all dimensions d >= 3k - 4, and all dimensions d >= 2k - 3 when G is bipartite. As a corollary, we have the following rainbow matching theorem which generalizes a result by Aharoni, Berger, Chudnovsky, Howard and Seymour: Let E1,. . . , E3k-2 be non-empty edge subsets of a graph and suppose that nu(E-i boolean OR E-j) > k for every i &NOTEQUexpressionL; j. Then E = U 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. (C) 2022 Elsevier Inc. All rights reserved.