Helly-Eigenschaft

Helly-Eigenschaft ist ein Begriff der Mathematik, genauer der kombinatorischen Mengenlehre.

Eine Familie F von Mengen hat genau dann die Helly-Eigenschaft, wenn jede Unterfamilie von F mit leerem Schnitt aus mindestens zwei disjunkten Mengen besteht^[1][2]. 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

Sei F eine Familie von Untermengen der Menge M. F hat genau dann die Helly-Eigenschaft, wenn jede Unterfamilie T von F folgende Aussage erfüllt:

$\cap_{S \in T} S = \empty \Rightarrow \exists S,S' \in T:S \cap S' = \empty$.

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

Beispiel

Betrachten wir eine Menge M von geschlossenen Interallen auf der realen Achse. Z.B. {[0,2],[1,5],[3,4]}. Die Menge ist so gewählt, dass der Schnitt aller Intervalle leer ist. Dann muss es zwei Intervalle A und B geben, von denen eine einen kleineren linken Endpunkt hat (ohne Beschränkung der Allgemeinheit A), als der rechte Endpunkt groß ist. Im Beispiel sind das [0,2] und [3,4]. Die Familie {A,B} hat daher immer einen leeren Schnitt. Mit anderen Worten A und B sind disjunkt. Also enthält jede Menge M von geschlossenen Interallen mit leerem Schnitt zwei disjunkte Intervalle und hat somit die Helly-Eigenschaft.

Gegenbeispiel

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 Hell-Eigenschaft.

Einzelnachweise

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).