서지주요정보
Topology of complexes of graphs with bounded matching number = 유계된 매칭 수를 가지는 그래프들로 이루어진 컴플렉스의 위상적 성질
서명 / 저자 Topology of complexes of graphs with bounded matching number = 유계된 매칭 수를 가지는 그래프들로 이루어진 컴플렉스의 위상적 성질 / Lee, Seunghun.
저자명 LEE, SEUNGHUN ; 이승훈
발행사항 [대전 : 한국과학기술원, 2020].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8036343

소장위치/청구기호

학술문화관(도서관)2층 패컬티라운지(학위논문)

DMAS 20013

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

리뷰정보

초록정보

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$로 줄일 수 있다. 연관된 또다른 협동적 다색 매칭 문제도 고려될 것이며, 특정 위상적 방법론이 이 문제에 적용가능하지 않아 보인다는 것을 예를 통해 입증한다.

서지기타정보

서지기타정보
청구기호 {DMAS 20013
형태사항 iv, 60 p. : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 이승훈
지도교수의 영문표기 : Andreas F. Holmsen
지도교수의 한글표기 : 안드레아스 홈슨
Including Appendix
학위논문 학위논문(박사) - 한국과학기술원 : 수리과학과,
서지주기 References : p. 55-57
주제 non-matching complexes
Leray complexes
graph complexes
discrete Morse theory
Gallai–Edmonds decomposition
rainbow matching
non-matching 컴플렉스
Leray 컴플렉스
그래프 컴플렉스
이산 모스 이론
Gallai–Edmonds 분할
다색 매칭
QR CODE qr code