In this paper, we study families of subtrees on a tree. Our first result gives a geometrical interpretation of a tree decomposition. We introduce acyclic families of convex bodies in $\mathds{R}^2$, which we call $\alpha$-decompositions, whose intersection graph contains a given graph as a subgraph. We then define an $\alpha$-dimension, which is the minimum value of the dimension of the nerve complex among all $\alpha$-decomposition for a graph. We prove that for a finite simple undirected graph, it is an intersection graph of a subtree family if and only if it is an intersection graph of an acyclic family of convex bodies in $\mathds{R}^2$. This implies that $\alpha$-dimension of a graph is same as the tree-width of the graph.
The second result is about the intersection patterns of subtree families. Helly`s theorem \cite{Hel23} states that if $\mathcal{F}$ is a finite family of convex sets in $\mathds{R}^d$ such that every $(d+1)$-tuple of $\mathcal{F}$ is intersecting, then the whole family $\mathcal{F}$ is intersecting. It is well-known that Helly`s theorem also holds for subtree families. We first prove that, for a subtree family $\mathcal{T}$ with two color classes, if every colorful pair of $\mathcal{T}$ is intersecting, then some color class is intersecting. This is a colorful version of Helly`s theorem for subtree families. We also show that, for every $0<\alpha\leq1$, there exists $0<\beta=\beta(\alpha)\leq1$ such that, for a subtree family $\mathcal{T}$, if only an $\alpha$ fraction of pairs of $\mathcal{T}$ are intersecting, then $\mathcal{T}$ has an intersecting subfamily containing a $\beta$ fraction of the subtrees in $\mathcal{T}$. This is a fractional version of Helly`s theorem for subtree families.
Finally, we prove a colorful version of fractional Helly theorem. That is, for every $0<\alpha\leq1$, there exists $0<\beta=\beta(\alpha)\leq1$ such that, for a subtree family $\mathcal{T}$ with two color classes, if only an $\alpha$ fraction of the colorful pairs of $\mathcal{T}$ are intersecting, then some color class has an intersecting subfamily containing $\beta$ fraction of the members in that color class. We extend this result to convex sets in $\mathds{R}^d$: For every $0<\alpha\leq1$, there exists $0<\beta=\beta(\alpha,d)\leq1$ such that, for any family $\mathcal{F}$ of convex sets in $\mathds{R}^d$ with $d+1$ color classes, if only an $\alpha$ fraction of the colorful $(d+1)$-tuples of $\mathcal{F}$ are intersecting, then some color class has an intersecting subfamily containing a $\beta$ fraction of the members in that color class. Moreover, we improve the lower bound for $\beta$, showing that $\beta$ tends to $1$ as $\alpha$ tends to $1$.
Subtree family의 교차 패턴에 대한 연구로, tree decomposition의 기하학적인 표현과 Helly 정리의 변형들에 대해 연구하였다. 첫 번째로 tree decomposition의 기하학적인 표현을 위하여 주어진 그래프 $G$에 대하여 intersection graph가 $G$를 포함하는 평면 위의 acyclic family of convex bodies를 구성하였으며, 이를 $\alpha$-decomposition이라 정의하였다. 가능한 모든 $\alpha$-decomposition 중 nerve complex의 차원의 최솟값을 $\alpha$-dimension이라 정의하였고, 그래프가 Subtree family의 intersection graph이기 위한 필요충분 조건이 평면 위의 비순환 볼록체족임을 증명하여, tree-width가 $\alpha$-dimension과 같음을 증명하였다.
두 번째로 subtree family의 교차 패턴을 관찰하기 위해 Helly 정리와 그 변형들이 subtree family에도 성립함을 증명하였다. Helly 정리는 $\mathds{R}^d$에서의 볼록집합들의 family에서 모든 $(d+1)$-짝이 intersecting subfamily일 때, 전체 family가 intersecting family가 되는 것을 말한다. Helly 정리가 Subtree family에 대해서도 성립함은 잘 알려진 사실이다. 우리는 먼저 두 개의 color class를 가지는 임의의 subtree family에 대하여, 모든 colorful 짝이 교차 할 때, 어떤 color class는 intersecting family를 구성함을 증명하였다. 이는 subtree family에 대한 Helly 정리의 colorful 표현이다. 다음으로, 임의의 subtree family에 대하여, $\alpha$ 비율 만큼의 짝만이 교차할 때, $\beta$ 비율만큼의 원소들이 intersecting subfamily를 구성함을 증명하였다. 이는 subtree family에 대한 Helly 정리의 fractional 표현이다.
세 번째로, subtree family에 대한 fractional Helly 정리의 colorful 표현을 증명하였다. 즉, 두 개의 color class를 가지는 임의의 subtree family에 대하여, $\alpha$ 비율 만큼의 colorful 짝이 교차 할 때, 어떤 color class는 $\beta$ 비율만큼의 원소들이 intersecting subfamily를 구성함을 증명하였다. 또한 $\beta$에 대한 기존의 경계를 개선하여 $\alpha$가 1로 수렴할수록 $\beta$가 1로 수렴함을 증명하였다. 마지막으로 colorful fractional Helly 정리를 $\mathds{R}^d$ 공간의 볼록집합들의 family에 대한 정리로 확장하였다.
