Loading Events

« All Events

  • This event has passed.

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

April 28 Tuesday @ 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.


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


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


Sang-il Oum (엄상일)
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.