Helly family

Helly family

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. In other words, any subfamily such that every (k+1)-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 (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.

Examples

* In the family of all subsets of the set {a,b,c,d}, the subfamily a,b,c}, {a,b,d}, {a,c,d}, {b,c,d 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 intervals of the real line 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 subsets of "E", such that, for any "G" ⊆ "F" with

:igcap_{Xin G} X=varnothing,

we can find "H" ⊆ "G" such that

:igcap_{Xin H} X=varnothing

and

:left|H ight|le k.

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 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 Domokos (arxiv|archive=math.AG|id=0511300) 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 (that is, a space with Helly dimension 1) 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.

References

*cite book
last = Balakrishnan
first = R.
coauthors = Ranganathan, K.
title = A textbook of graph theory
publisher = New York: Springer
date = 2000
pages =
isbn = 0387988599 (acid-free paper)

*cite book
last = Kloks
first = Ton
title = Treewidth: computations and approximations
publisher = Berlin; New York: Springer-Verlag
date = 1994
pages =
isbn = 3540583564


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Helly's theorem — In geometry, Helly s theorem is a basic combinatorial result on convex sets. It was proved by Eduard Helly in 1923, and gave rise to the notion of Helly family.tatement of Helly s theorem:Suppose that::X 1,X 2,dots,X n :is a finite collection of… …   Wikipedia

  • Circular-arc graph — A circular arc graph (left) and a corresponding arc model (right). In graph theory, a circular arc graph is the intersection graph of a set of arcs on the circle. It has one vertex for each arc in the set, and an edge between every pair of… …   Wikipedia

  • List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia

  • List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • Median graph — The median of three vertices in a median graph In mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest… …   Wikipedia

  • combinatorics — /keuhm buy neuh tawr iks, tor , kom beuh /, n. (used with singular v.) See combinatorial analysis. * * * Branch of mathematics concerned with the selection, arrangement, and combination of objects chosen from a finite set. The number of possible… …   Universalium

  • Shetland — For other uses, see Shetland (disambiguation). Shetland Sealtainn …   Wikipedia

  • Shetland — Pour les articles homonymes, voir Shetland (homonymie). Shetland Sealtainn (gd) …   Wikipédia en Français

  • Scandinavian Scotland — History of Scotland This article is part of a series Chronologicy …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”