Helly property

Helly property is a term used in mathematics, more precisely in combinatorial set theory . A family of sets has the Helly property if and only if every subfamily with an empty cut contains at least two disjoint sets. The Helly property plays an important role in combinatorics and discrete mathematics . It was motivated by a sentence about convex sets by Eduard Helly (1884–1943).

Formal definition

Be a family of subsets of a set . The family has the Helly property if and only if each subfamily of satisfies the following statement: ${\ displaystyle F}$ ${\ displaystyle M}$ ${\ displaystyle F}$ ${\ displaystyle T}$ ${\ displaystyle F}$

{\ displaystyle \ bigcap _ {S \ in T} S = \ emptyset \; \ Rightarrow \; \ exists S, S '\ in T: S \ cap S' = \ emptyset}

.

In words: If a subfamily consists of sets whose common intersection is empty, then it contains two sets whose pairwise intersection is empty. ${\ displaystyle T}$ ${\ displaystyle T}$

example

Let us consider a set of closed real intervals, e.g. B. . The amount is chosen so that the intersection of all intervals is empty. Then there must be two intervals and , one of which has a smaller left end point ( without loss of generality ) than the right end point is large. In the example these are and and these two sets are disjoint. So any set of closed intervals with an empty cut contains two disjoint intervals. The set of all closed intervals thus has the Helly property. ${\ displaystyle T}$ ${\ displaystyle T = \ {[0.2], [1.5], [3.4] \}}$ ${\ displaystyle A}$ ${\ displaystyle B}$ ${\ displaystyle A}$ ${\ displaystyle [0,2]}$ ${\ displaystyle [3,4]}$ ${\ displaystyle T}$

Counterexample

Suppose we have a family of the sets A, B, C and D. A overlaps with B and C, as well as B and C, but there is no element that is contained in both A, B and C. D only overlaps with C. Then the subfamily of A, B and C has an empty cut. But the family does not contain two disjoint sets, so we have found an empty cut subfamily that does not contain two disjoint sets. Hence, A, B, C, D does not have the Helly property.

Individual evidence

↑ C. Berge: Hypergraphs. North Holland, Amsterdam 1989.
↑ Victor Chepoi, Nadia Creignou, Miki Hermann, Gernot Salzer: The Helly property and satisfiability of Boolean formulas defined on set families. In: European Journal of Combinatorics. Volume 31, Issue 2, Combinatorics and Geometry, February 2010, ISSN 0195-6698 pp. 502-516. ( PDF file ).

[1] C. Berge: Hypergraphs. North Holland, Amsterdam 1989.

[chepoi-2] Victor Chepoi, Nadia Creignou, Miki Hermann, Gernot Salzer: The Helly property and satisfiability of Boolean formulas defined on set families. In: European Journal of Combinatorics. Volume 31, Issue 2, Combinatorics and Geometry, February 2010, ISSN 0195-6698 pp. 502-516. ( PDF file ).