Helly family

In combinatorics, a Helly family of order k is a family of sets in which every minimal subfamily with an empty intersection has k or fewer sets in it.

[1] The k-Helly property is the property of being a Helly family of order k.[2] 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

These concepts are named after Eduard Helly (1884–1943); 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.

[1] More formally, a Helly family of order k is a set system (V, E), 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.

For instance, the open intervals of the real line satisfy the Helly property for finite subcollections, but not for infinite subcollections: the intervals (0,1/i) (for i = 0, 1, 2, ...) have pairwise nonempty intersections, but have an empty overall intersection.

If a family of sets is a Helly family of order k, that family is said to have Helly number k. 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.

[4] 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.[5] 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.

[6] Helly dimension has also been applied to other mathematical objects.

For instance Domokos (2007) defines the Helly dimension of a group (an algebraic structure formed by an invertible and associative binary operation) to be one less than the Helly number of the family of left cosets of the group.

[7] 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.

[1][2] A convex metric space in which the closed balls have the 2-Helly property (that is, a space with Helly dimension 1, in the stronger variant of Helly dimension for infinite subcollections) is called injective or hyperconvex.

[8] The existence of the tight span allows any metric space to be embedded isometrically into a space with Helly dimension 1.

Each hyperedge of a hypergraph is a set of vertices. No vertex is shared by all 4 edges. Some subfamilies with 3 edges created by removing an edge are non-intersecting (edges 1, 3 and 4), but others aren't (edges 1, 2 and 3 which all share vertex 3), so the 4 edge family is not minimal. However, it isn't possible to remove an edge from either of the non-intersecting 3 edge subfamilies to get a non-intersecting 2 edge subfamily. Thus, the edges form a Helly family of order 3.