Helly family

Helly property is a term in mathematics, specifically the combinatorial set theory.

A family F of sets has exactly then the Helly property when every subfamily of F with empty intersection contains at least two disjoint sets. The Helly property plays an important role in combinatorics and discrete mathematics. It was motivated by a theorem on convex sets by Eduard Helly ( 1884-1943 ).

Formal definition

Let F be a family of subsets of the set M. F has exactly then the Helly property when every subfamily T of F satisfies the following statement:

.

In words: when a subfamily T consists of sets whose common intersection is empty, then T contains two sets whose pairwise intersection is empty.

Example

Consider a set M of closed intervals on the real axis. For example, { [0,2], [1,5], [3,4 ]}. The amount is chosen so that the intersection of all intervals is empty. Then there must be two intervals A and B type, one of which has a smaller left endpoint ( without loss of generality A) than the right endpoint is great. In the example, the [0,2] and [3,4]. The family {A, B} always has therefore an empty intersection. In other words, A and B are disjoint. So any set M of closed intervals with empty intersection contains two disjoint intervals and thus has the Helly property.

Counterexample

Suppose we have a family of the quantities A, B, C and D. A overlaps B and C, as well as B and C, but there is no element that is included in both A, B and C. D overlaps only with C. Then B and C has the subfamily of A, an empty intersection. But the family does not contain two disjoint sets, and thus we have found a subfamily with empty intersection, which does not contain two disjoint sets. Therefore, A, B, C, D does not have the light property.