Helly-Eigenschaft

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 einen Satz über konvexe Mengen von Eduard Helly (1884–1943) motiviert.

Formale Definition

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

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

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

Beispiel

Betrachten wir eine Menge $T$ von abgeschlossenen reellen Intervallen, z. B. $T=\{[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]$ und diese beiden Mengen sind disjunkt. Also enthält jede Menge $T$ von abgeschlossenen Intervallen mit leerem Schnitt zwei disjunkte Intervalle. Die Menge aller abgeschlossenen Intervalle hat also 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 Helly-Eigenschaft.