In combinatorics, a Helly family of order k is a family of setssuch that any minimal subfamily with an empty intersection has k or fewer sets in it. Equivalently, every finite subfamily such that every -fold intersection is non-empty has non-empty total intersection. The k-Helly property is the property of being a Helly family of order k. The number k is frequently omitted from these names in the case that k = 2. Thus, a set-family has the Helly property if for every n sets in the family, if, then. These concepts are named after Eduard Helly ; Helly's theorem on convex sets, which gave rise to this notion, states that convex sets in Euclidean space of dimension n are a Helly family of order n + 1.
Examples
In the family of all subsets of the set, the subfamily has an empty intersection, but removing any set from this subfamily causes it to have a nonempty intersection. Therefore, it is a minimal subfamily with an empty intersection. It has four sets in it, and is the largest possible minimal subfamily with an empty intersection, so the family of all subsets of the set is a Helly family of order 4.
Let I be a finite set of closed intervals of the real line with an empty intersection. Let A be the interval whose left endpoint a is as large as possible, and let B be the interval whose right endpoint b is as small as possible. Then, if a were less than or equal tob, all numbers in the range would belong to all intervals of I, violating the assumption that the intersection of I is empty, so it must be the case that a > b. Thus, the two-interval subfamily has an empty intersection, and the family I cannot be minimal unless I = . Therefore, all minimal families of intervals with empty intersections have two or fewer intervals in them, showing that the set of all intervals is a Helly family of order 2.
More formally, a Helly family of order k is a set system, with E a collection of subsets of V, such that, for every finite G ⊆ E with we can find H ⊆ G such that and In some cases, the same definition holds for every subcollection G, regardless of finiteness. However, this is a more restrictive condition. For instance, the open intervals of the real line satisfy the Helly property for finite subcollections, but not for infinite subcollections: the intervals have pairwise nonempty intersections, but have an empty overall intersection.
Helly dimension
If a family of sets is a Helly family of order k, that family is said to have Helly numberk. The Helly dimension of a metric space is one less than the Helly number of the family of metric balls in that space; Helly's theorem implies that the Helly dimension of a Euclidean space equals its dimension as a real vector space. The Helly dimension of a subset S of a Euclidean space, such as a polyhedron, is one less than the Helly number of the family of translates of S. For instance, the Helly dimension of any hypercube is 1, even though such a shape may belong to a Euclidean space of much higher dimension. Helly dimension has also been applied to other mathematical objects. For instance defines the Helly dimension of a group to be one less than the Helly number of the family of left cosets of the group.
The Helly property
If a family of nonempty sets has an empty intersection, its Helly number must be at least two, so the smallest k for which the k-Helly property is nontrivial is k = 2. The 2-Helly property is also known as the Helly property. A 2-Helly family is also known as a Helly family. A convex metric space in which the closed balls have the 2-Helly property is called injective or hyperconvex. The existence of the tight span allows any metric space to be embedded isometrically into a space with Helly dimension 1.
The Helly property in hypergraphs
A hypergraph is equivalent to a set-family. In hypergraphs terms, a hypergraph H = has the Helly property if for every n hyperedges in E, if, then. For every hypergraph H, the following are equivalent:
