In combinatorics

Combinatorics

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...

, a Helly family of order k is a family of sets such that any minimal subfamily with an empty intersection has k or fewer sets in it. In other words, any 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. These concepts are named after Eduard Helly

Eduard Helly

Eduard Helly was a mathematician and the eponym of Helly's theorem, Helly families, Helly's selection theorem, Helly metric, and the Helly–Bray theorem. In 1912, Helly published a proof of Hahn–Banach theorem, 15 years before Hahn and Banach discovered it independently...

 (1884 - 1943); Helly's theorem

Helly's theorem

Helly's theorem is a basic result in discrete geometry describing the ways that convex sets may intersect each other. It was discovered by Eduard Helly in 1913, but not published by him until 1923, by which time alternative proofs by and had already appeared...

 on convex set

Convex set

In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...

s, which gave rise to this notion, states that convex sets in Euclidean space

Euclidean space

In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...

 of dimension n are a Helly family of order n + 1.

Examples

• In the family of all subsets of the set {a,b,c,d}, 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 {a,b,c,d} is a Helly family of order 4.

• Let I be a set of closed interval
  Interval
  Interval may refer to:* Interval , a range of numbers * Interval measurements or interval variables in statistics is a level of measurement...
  
  s of the real line
  Real line
  In mathematics, the real line, or real number line is the line whose points are the real numbers. That is, the real line is the set of all real numbers, viewed as a geometric space, namely the Euclidean space of dimension one...
  
   with an empty intersection. Then there must be two intervals A and B in I such that the left endpoint of A is larger than the right endpoint of B. {A,B} have an empty intersection, so I cannot be minimal unless I={A,B}. Therefore, all minimal families of intervals with empty intersections have 2 or fewer intervals in them, and the set of all intervals is a Helly family of order 2.

Formal definition

More formally, a Helly family of order k is a set system (F, E), with F a collection of subset

Subset

In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

s of E, such that, for any G ⊆ F with


we can find H ⊆ G such that


and

Helly dimension

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

Metric space

In mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean 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

Vector space

A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...

.

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

Translation (geometry)

In Euclidean geometry, a translation moves every point a constant distance in a specified direction. A translation can be described as a rigid motion, other rigid motions include rotations and reflections. A translation can also be interpreted as the addition of a constant vector to every point, or...

 of S. For instance, the Helly dimension of any hypercube

Hypercube

In geometry, a hypercube is an n-dimensional analogue of a square and a cube . It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perpendicular to each other and of the same length.An...

 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 M. Domokos 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

Metric space

In mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...

 in which the closed balls

Ball (mathematics)

In mathematics, a ball is the space inside a sphere. It may be a closed ball or an open ball ....

 have the 2-Helly property (that is, a space with Helly dimension 1) is called injective

Injective metric space

In metric geometry, an injective metric space, or equivalently a hyperconvex metric space, is a metric space with certain properties generalizing those of the real line and of L∞ distances in higher-dimensional vector spaces...

 or hyperconvex. The existence of the tight span

Tight span

In metric geometry, the metric envelope or tight span of a metric space M is an injective metric space into which M can be embedded. In some sense it consists of all points "between" the points of M, analogous to the convex hull of a point set in a Euclidean space. The tight span is also sometimes...

 allows any metric space to be embedded isometrically into a space with Helly dimension 1.

See also

• Radon's theorem
  Radon's theorem
  In geometry, Radon's theorem on convex sets, named after Johann Radon, states that any set of d + 2 points in Rd can be partitioned into two sets whose convex hulls intersect...
  
  
• Carathéodory's theorem
  Carathéodory's theorem (convex hull)
  In convex geometry Carathéodory's theorem states that if a point x of Rd lies in the convex hull of a set P, there is a subset P′ of P consisting of d+1 or fewer points such that x lies in the convex hull of P′. Equivalently, x lies in an r-simplex with vertices in P, where r \leq d...