Loading Events

« All Events

  • This event has passed.

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

Tuesday, April 28, 2020 @ 4:30 PM - 5:30 PM KST

Room B232, IBS (기초과학연구원)


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.


Tuesday, April 28, 2020
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:


Room B232
IBS (기초과학연구원)


Sang-il Oum (엄상일)
View Organizer Website
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.