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. Die Helly-Eigenschaft spielt in der Kombinatorik und diskreten Mathematik eine wichtige Rolle. Sie wurde durch ein 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
- 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. Band 31, Issue 2, Combinatorics and Geometry, Februar 2010, ISSN 0195-6698 S. 502–516. (PDF-Datei).