Seunghun Lee (이승훈) gave a talk on the complexes of subgraphs having no large matching at the Discrete Math Seminar

On April 28, 2020, Seunghun Lee (이승훈) from KAIST presented a talk on the topological property of the non-matching complex, that is a simplicial complex consisting of subgraphs on the same vertex set having no matching of size k and its application to the rainbow matching problem of graphs. The title of his talk is “Leray numbers of complexes of graphs with bounded matching number“.

Seunghun Lee (이승훈), Leray numbers of complexes of graphs with bounded matching number

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’ \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 $\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\geq 3k-4$, and all dimensions $d \geq 2k-3$ when $G$ is bipartite. 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, \dots, 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\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.

This is a joint work with Andreas Holmsen.