Helly-Eigenschaft ist ein Begriff der Mathematik, genauer der kombinatorischen Mengenlehre. Eine Familie von Mengen hat genau dann die Helly-Eigenschaft, wenn jede Unterfamilie mit leerem Schnitt mindestens zwei disjunkte Mengen enthält.[1][2] Die Helly-Eigenschaft spielt in der Kombinatorik und diskreten Mathematik eine wichtige Rolle. Sie wurde durch einen Satz über konvexe Mengen von Eduard Helly (1884–1943) motiviert.

Formale Definition

Bearbeiten

Sei   eine Familie von Teilmengen einer Menge  . Die Familie   hat genau dann die Helly-Eigenschaft, wenn jede Unterfamilie   von   folgende Aussage erfüllt:

 .

In Worten: Wenn eine Unterfamilie   aus Mengen besteht, deren gemeinsamer Schnitt leer ist, dann enthält   zwei Mengen, deren paarweiser Schnitt leer ist.

Beispiel

Bearbeiten

Betrachten wir eine Menge   von abgeschlossenen reellen Intervallen, z. B.  . Die Menge ist so gewählt, dass der Schnitt aller Intervalle leer ist. Dann muss es zwei Intervalle   und   geben, von denen eine einen kleineren linken Endpunkt hat (ohne Beschränkung der Allgemeinheit  ), als der rechte Endpunkt groß ist. Im Beispiel sind das   und   und diese beiden Mengen sind disjunkt. Also enthält jede Menge   von abgeschlossenen Intervallen mit leerem Schnitt zwei disjunkte Intervalle. Die Menge aller abgeschlossenen Intervalle hat also die Helly-Eigenschaft.

Gegenbeispiel

Bearbeiten

Angenommen wir haben eine Familie aus den Mengen A, B, C und D. A überlappt mit B und C, wie auch B und C, aber es gibt kein Element, das sowohl in A, B als auch C enthalten ist. D überlappt allein mit C. Dann hat die Unterfamilie aus A, B und C einen leeren Schnitt. Aber die Familie enthält keine zwei disjunkte Mengen und somit haben wir eine Unterfamilie mit leerem Schnitt gefunden, die keine zwei disjunkten Mengen enthält. Daher hat A, B, C, D nicht die Helly-Eigenschaft.

Einzelnachweise

Bearbeiten
  1. C. Berge: Hypergraphs. North-Holland, Amsterdam 1989.
  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. Band 31, Issue 2, Combinatorics and Geometry, Februar 2010, ISSN 0195-6698 S. 502–516. (PDF-Datei).