Helly's theorem is a classical result about intersection patterns of convex sets in Euclidean spaces. It states that every finite family of convex sets in $R^d$ is intersecting if every d+1 or fewer members are intersecting. There are a large number of generalizations and applications of Helly's theorem. For instance, the colorful and fractional Helly theorems and the (p,q)-theorem are important generalizations. It was proved by Alon et al. that the fractional Helly property is a key ingredient when establishing the (p,q)-theorem for abstract set-systems. Hence it has been one of the most fundamental questions in this field to find a sufficient condition that makes a non-empty family of sets satisfies the fractional Helly property. In this dissertation, we give an overview of classical Helly type theorems, and prove some combinatorial generalizations of Helly's theorem with a focus on the fractional Helly properties.
Our first main topic is a combination of the colorful Helly theorem and the fractional Helly theorem. We introduce a purely combinatorial method to improve the bound of $B\'{a}r\'{a}ny$ et al.'s colorful fractional Helly theorem for convex sets. This proof technique can be easily modified to achieve a colorful fractional Helly theorem for abstract set-systems. The second main topic is about Helly type theorems for certain families of graphs. A connected cover in a graph G is a non-empty family $\mathcal{G}$ of induced subgraphs in G such that every non-empty intersection is connected. We prove some Helly type theorems for connected covers in graphs without large complete minors. In particular, the results on connected covers in planar graphs can be applied for set-systems which are more general than good covers in the plane.
Helly 정리는 유클리드 공간에서의 볼록집합들의 교차 패턴에 관한 고전적인 결과로 $R^d$의 유한한 개수의 볼록집합들이 주어져 있을 때 d+1 혹은 그 이하의 개수의 볼록집합들마다 교차하면 모든 몰록집합들이 교차한다는 내용을 말한다. 지난 수십 년간 Helly 정리의 일반화와 응용에 대한 연구가 진행되었는데 그 중에서도 중요한 일반화로 colorful Helly 정리, fractional Helly 정리, (p,q)-정리 등이 있다. 특히 fractional Helly 성질은 추상적인 집합계에서의 (p,q)-정리를 증명하는 데에 핵심 역할을 한다고 알려짐에 따라 fractional Helly 성질을 가지기 위한 충분조건을 찾는 것은 이 분야에서 가장 기본적인 질문으로 제시되고 있다. 본 학위논문에서는 Helly형 정리들에 대한 개요를 설명하고 최근 증명한 Helly 정리의 조합적인 일반화들을 소개하고자 한다.
본 논문의 첫 주제는 colorful Helly 정리와 fractional Helly 정리의 융합이다. 볼록집합들의 모임에 대한 기존의 colorful fractional Helly 정리의 결과를 향상시킬 수 있는 순수 조합적인 방법을 소개하고 이를 이용하여 볼록집합들의 모임 및 추상적인 집합계에 대한 colorful fractional Helly 정리들을 증명하였다. 두 번째 주제는 교집합이 연결된 그래프인 그래프들의 모임에 대한 Helly형 정리들이다. 주어진 그래프 $G$에 대하여 모든 교집합이 연결된 그래프인 유도된 부분 그래프들의 모임을 connected cover라고 정의하며 본 논문에서는 fractional Helly 성질에 중점을 두고 큰 완전 그래프를 마이너로 가지지 않는 그래프에서의 connected cover들에 대한 Helly형 정리들을 증명하였다. 특히 평면 그래프에서의 connected cover에 대한 결과들은 평면 위의 good cover보다 더 일반적인 집합계에 대해 적용할 수 있다.
