Helly family

Last updated

In combinatorics, 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. Equivalently, every finite subfamily such that every -fold intersection is non-empty has non-empty total intersection. [1] The k-Helly property is the property of being a Helly family of order k. [2]

Contents

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 (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]

Examples

Formal definition

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 GE with

we can find HG such that

and

[1]

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 (0,1/i) (for i = 0, 1, 2, ...) 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. [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]

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

The Helly property in hypergraphs

A hypergraph is equivalent to a set-family. In hypergraphs terms, a hypergraph H = (V, E) has the Helly property if for every n hyperedges in E, if , then . [10] :467 For every hypergraph H, the following are equivalent: [10] :470-471

Related Research Articles

Compact space Topological notions of all points being "close"

In mathematics, more specifically in general topology, compactness is a property that generalizes the notion of a subset of Euclidean space being closed and bounded. Examples include a closed interval, a rectangle, or a finite set of points. This notion is defined for more general topological spaces than Euclidean space in various ways.

Connected space Topological space that is connected

In topology and related branches of mathematics, a connected space is a topological space that cannot be represented as the union of two or more disjoint non-empty open subsets. Connectedness is one of the principal topological properties that are used to distinguish topological spaces.

Convex set In geometry, set that intersects every line into a single line segment

In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points, it contains the whole line segment that joins them. Equivalently, a convex set or a convex region is a subset that intersect every line into a single line segment . For example, a solid cube is a convex set, but anything that is hollow or has an indent, for example, a crescent shape, is not convex.

In measure theory, a branch of mathematics, the Lebesgue measure, named after French mathematician Henri Lebesgue, is the standard way of assigning a measure to subsets of n-dimensional Euclidean space. For n = 1, 2, or 3, it coincides with the standard measure of length, area, or volume. In general, it is also called n-dimensional volume, n-volume, or simply volume. It is used throughout real analysis, in particular to define Lebesgue integration. Sets that can be assigned a Lebesgue measure are called Lebesgue-measurable; the measure of the Lebesgue-measurable set A is here denoted by λ(A).

Measure (mathematics) Generalization of length, area, volume and integral

In mathematical analysis, a measure on a set is a systematic way to assign a number to each suitable subset of that set, intuitively interpreted as its size. In this sense, a measure is a generalization of the concepts of length, area, and volume. A particularly important example is the Lebesgue measure on a Euclidean space, which assigns the conventional length, area, and volume of Euclidean geometry to suitable subsets of the n-dimensional Euclidean space Rn. For instance, the Lebesgue measure of the interval [0, 1] in the real numbers is its length in the everyday sense of the word, specifically, 1.

Open set Basic subset of a topological space

In mathematics, particularly in topology, an open set is an abstract concept generalizing the idea of an open interval in the real line. The simplest example is in metric spaces, where open sets can be defined as those sets which contain a ball around each of their points ; however, an open set, in general, can be very abstract: any collection of sets can be called open, as long as the union of an arbitrary number of open sets in the collection is open, the intersection of a finite number of open sets is open, and the space itself is open. These conditions are very loose, and they allow enormous flexibility in the choice of open sets. In the two extremes, every set can be open, or no set can be open but the space itself and the empty set.

Disjoint sets sets with no element in common

In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set. For example, {1, 2, 3} and {4, 5, 6} are disjoint sets, while {1, 2, 3} and {3, 4, 5} are not disjoint. A collection of more than two sets is called disjoint if any two distinct sets of the collection are disjoint.

In mathematics, a baseB of a topology on a set X is a collection of subsets of X that is stable by finite intersection. A base defines a topology on X that has, as open sets, all unions of elements of B.

In real analysis the Heine–Borel theorem, named after Eduard Heine and Émile Borel, states:

In combinatorics, the Erdős–Ko–Rado theorem of Paul Erdős, Chao Ko, and Richard Rado is a theorem on intersecting set families.

In general topology, a branch of mathematics, a collection A of subsets of a set X is said to have the finite intersection property (FIP) if the intersection over any finite subcollection of A is non-empty. It has the strong finite intersection property (SFIP) if the intersection over any finite subcollection of A is infinite.

In topology, a subbase for a topological space X with topology T is a subcollection B of T that generates T, in the sense that T is the smallest topology containing B. A slightly different definition is used by some authors, and there are other useful equivalent formulations of the definition; these are discussed below.

Minkowski addition Sums vector sets A and B by adding each vector in A to each vector in B

In geometry, the Minkowski sum of two sets of position vectors A and B in Euclidean space is formed by adding each vector in A to each vector in B, i.e., the set

In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets.

Hellys theorem theorem about the intersections of d-dimensional convex sets

Helly's theorem is a basic result in discrete geometry on the intersection of convex sets. It was discovered by Eduard Helly in 1913, but not published by him until 1923, by which time alternative proofs by Radon (1921) and König (1922) had already appeared. Helly's theorem gave rise to the notion of a Helly family.

In measure theory, Carathéodory's extension theorem states that any pre-measure defined on a given ring R of subsets of a given set Ω can be extended to a measure on the σ-algebra generated by R, and this extension is unique if the pre-measure is σ-finite. Consequently, any pre-measure on a ring containing all intervals of real numbers can be extended to the Borel algebra of the set of real numbers. This is an extremely powerful result of measure theory, and leads, for example, to the Lebesgue measure.

In mathematics, the Vitali covering lemma is a combinatorial and geometric result commonly used in measure theory of Euclidean spaces. This lemma is an intermediate step, of independent interest, in the proof of the Vitali covering theorem. The covering theorem is credited to the Italian mathematician Giuseppe Vitali. The theorem states that it is possible to cover, up to a Lebesgue-negligible set, a given subset E  of Rd by a disjoint family extracted from a Vitali covering of E.

The Banach–Tarski paradox is a theorem in set-theoretic geometry, which states the following: Given a solid ball in 3‑dimensional space, there exists a decomposition of the ball into a finite number of disjoint subsets, which can then be put back together in a different way to yield two identical copies of the original ball. Indeed, the reassembly process involves only moving the pieces around and rotating them without changing their shape. However, the pieces themselves are not "solids" in the usual sense, but infinite scatterings of points. The reconstruction can work with as few as five pieces.

Cantor's intersection theorem refers to two closely related theorems in general topology and real analysis, named after Georg Cantor, about intersections of decreasing nested sequences of non-empty compact sets.

In mathematics, a polyadic space is a topological space that is the image under a continuous function of a topological power of an Alexandroff one-point compactification of a discrete topological space.

References

  1. 1 2 3 4 Bollobás, Béla (1986), Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability, Cambridge University Press, p. 82, ISBN   9780521337038 .
  2. 1 2 3 Duchet, Pierre (1995), "Hypergraphs", in Graham, R. L.; Grötschel, M.; Lovász, L. (eds.), Handbook of combinatorics, Vol. 1, 2, Amsterdam: Elsevier, pp. 381–432, MR   1373663 . See in particular Section 2.5, "Helly Property", pp. 393–394.
  3. This is the one-dimensional case of Helly's theorem. For essentially this proof, with a colorful phrasing involving sleeping students, see Savchev, Svetoslav; Andreescu, Titu (2003), "27 Helly's Theorem for One Dimension", Mathematical Miniatures, New Mathematical Library, 43, Mathematical Association of America, pp. 104–106, ISBN   9780883856451 .
  4. Martini, Horst (1997), Excursions Into Combinatorial Geometry, Springer, pp. 92–93, ISBN   9783540613411 .
  5. Bezdek, Károly (2010), Classical Topics in Discrete Geometry, Springer, p. 27, ISBN   9781441906007 .
  6. Sz.-Nagy, Béla (1954), "Ein Satz über Parallelverschiebungen konvexer Körper", Acta Universitatis Szegediensis, 15: 169–177, MR   0065942, archived from the original on 2016-03-04, retrieved 2013-09-10.
  7. Domokos, M. (2007), "Typical separating invariants", Transformation Groups, 12 (1): 49–63, arXiv: math/0511300 , doi:10.1007/s00031-005-1131-4, MR   2308028 .
  8. Deza, Michel Marie; Deza, Elena (2012), Encyclopedia of Distances, Springer, p. 19, ISBN   9783642309588
  9. Isbell, J. R. (1964), "Six theorems about injective metric spaces", Comment. Math. Helv., 39: 65–76, doi:10.1007/BF02566944 .
  10. 1 2 Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, 29, North-Holland, ISBN   0-444-87916-1, MR   0859549