Given a graph $G$ on the vertex set $V$, the non-matching complex of $G$, $NM_{k}(G)$, is the family of subgraphs $G'\subset G$ whose matching number $\nu(G')$ is strictly less than $k$. As an attempt to generalize the result by Linusson, Shareshian and Welker on the homotopy types of $NM_{k}(K_{n})$ and $NM_{k}(K_{r,s})$ to arbitrary graphs G, we show that (i) $NM_{k}(G)$ is $(3k − 3)$-Leray, and (ii) if $G$ is bipartite, then $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 $NM_{k}(G)$, which vanishes in all dimensions $d \geq 3k − 4$, and all dimensions $d \geq 2k − 3$ when $G$ is bipartite. Following a similar line of the proof, we answer a question raised by Linusson et al. on the homotopy type of $NM_{k}(G)$ when $G$ is a complete multipartite graph with a vertex class consisting of a single vertex.
As a corollary, we have the following rainbow matching theorem which generalizes the result by Aharoni et. al. and Drisko’s theorem: Let $E_1 , . . . , E_{3k−2}$ be non-empty edge subsets of a graph and suppose that $\nu(E_{i} \cup E_j) \geq k$ for every $i \neq 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. We also consider a related collaborative rainbow matching problem, and construct examples showing that certain topological methods do not seem to be applicable.
꼭지점들의 집합 $V$ 위에 주어진 그래프 $G$에 대해서, $G$의 non-matching 컴플렉스 $NM_{k}(G)$를 매칭 수 $\nu(G')$이 $k$보다 작은 $G$의 부분그래프 $G'$들의 모임으로 정의하자. Linusson, Shareshian, Welker의 $NM_{k}(K_n)$와 $NM_{k}(K_{r,s})$의 호모토피 타입에 대한 결과를 일반적인 그래프 $G$로 일반화하기 위한 시도로서, 이 연구는 (i) $NM_{k}(G)$가 $(3k − 3)$-Leray이며, (ii) $G$가 bipartite인 경우에는 $NM_{k}(G)$가 $(2k − 2)$-Leray임을 보인다. 이 결과는 $NM_{k}(G)$의 공집합이 아닌 face들의 링크들의 호몰로지 군을 분석함으로써 얻어질 수 있는데, 이는 차원 $d$가 $3k − 4$ 이상인 경우에 영이 되며, $G$가 bipartite인 경우에는 $d$가 $2k − 3$ 이상인 경우에 영이 된다. 비슷한 증명 과정을 이용하여, $G$가 완전 multipartite 그래프인 경우에 $NM_{k}(G)$의 호모토피 타입이 무엇인지에 대한 Linusson 등의 질문을, 어떤 꼭지점 모임의 크기가 1인 경우에 한해 답한다.
이의 따름정리로서 Aharoni 등의 결과와 Drisko의 정리를 일반화하는 다음의 다색 매칭 정리를 유도한다: $E_1 , . . . , E_{3k−2}$를 공집합이 아닌 edge 집합이라고 하고, 서로 다른 $i$와 $j$에 대해서 $\nu(E_{i} \cap E_{j}) \geq k$를 만족한다고 가정하자. 그러면, $E = \bigcup E_{i}$ 는 $k$ 크기의 다색 매칭을 가진다. 또한 $E$가 bipartite 그래프의 edge 집합인 경우에는 필요한 edge 집합들의 개수를 $2k − 1$로 줄일 수 있다. 연관된 또다른 협동적 다색 매칭 문제도 고려될 것이며, 특정 위상적 방법론이 이 문제에 적용가능하지 않아 보인다는 것을 예를 통해 입증한다.
