The Knaster–Kuratowski–Mazurkiewicz (KKM) theorem is a powerful tool in many areas of mathematics. In this paper we introduce a version of the KKM theorem for trees and use it to prove several combinatorial theorems.
A
2-tree hypergraph is a family of nonempty subsets of
T 
R (where
T and
R are trees), each of which has a connected intersection with
T and with
R. A
homogeneous 2-tree hypergraph is a family of subsets of
T each of which is the union of two connected sets.
For each such hypergraph
H we denote by
(
H) the minimal cardinality of a set intersecting all sets in the hypergraph and by
(
H) the maximal number of disjoint sets in it.
In this paper we prove that in a 2-tree hypergraph
(
H)
2
(
H) and in a homogeneous 2-tree hypergraph
(
H)
3
(
H). This improves the result of Alon [3], that
(
H)
8
(
H) in both cases.
Similar results are proved for d-tree hypergraphs and homogeneous d-tree hypergraphs, which are defined in a similar way. All the results improve the results of Alon [3] and generalize the results of Kaiser [1] for intervals.
Mathematics Subject Classification (2000):
05B40