Schnittfamilie

Eine Schnittfamilie einer Menge <math>N</math> bezeichnet in der Mathematik eine Familie von Teilmengen von <math>N</math>, bei der je zwei ihrer Elemente einen nichtleeren Schnitt haben.

Definition

Eine Mengenfamilie <math>F \subseteq \mathcal{P}(N)</math> wird als Schnittfamilie bezeichnet, wenn folgende Eigenschaft erfüllt ist:

Für alle <math>A_i,A_j \in F</math> gilt <math>A_i \cap A_j \neq \varnothing</math>.

Bemerkungen

Die maximale Mächtigkeit einer Schnittfamilie <math>F </math> einer endlichen Menge <math>N</math> der Mächtigkeit <math>n</math> ist <math> |F| \leq 2^{n-1} </math>.

Jeder Filter ist eine Schnittfamilie.<ref>Stasys Jukna: Extremal Combinatorics. Springer, Berlin 2001, ISBN 3-540-66313-4, S. 90.</ref>

Eine <math>k</math>-Schnittfamilie bezeichnet eine Schnittfamilie, in der alle Elemente die Mächtigkeit <math>k</math> haben. Zu maximalen Mächtigkeiten solcher Familien macht der Satz von Erdős-Ko-Rado eine Aussage.

Nach dem Satz von Kleitman hat die Vereinigung von <math>m</math> Schnittfamilien <math>\bar F = \bigcup_{i=1}^m F_i</math> höchstens <math>|\bar F| \leq 2^n - 2^{n-m}</math> Teilmengen.<ref>Stasys Jukna: Extremal Combinatorics. Springer, Berlin 2001, ISBN 3-540-66313-4, S. 91.</ref>

Quellen

Martin Aigner, Günter M. Ziegler: Das BUCH der Beweise. Springer, Berlin 2002, ISBN 3-540-42535-7 (3. Auflage: ISBN 978-3-642-02258-6)
Stasys Jukna: Extremal Combinatorics. Springer, Berlin 2001, ISBN 3-540-66313-4.

Einzelnachweise