Schnittfamilie

Eine Schnittfamilie F einer N-Menge bezeichnet in der Mathematik eine endliche Familie, bei der je zwei ihrer Elemente einen nichtleeren Schnitt haben.

Definition

Eine Familie wird als Schnittfamilie F bezeichnet, wenn folgende Eigenschaft erfüllt ist:

$\forall A_i,A_j \in F: A_i \cap A_j \neq \varnothing$

Bemerkungen

Die maximale Mächtigkeit einer Schnittfamilie F ist durch $|F| \leqslant 2^{n-1}$ beschränkt.

Jeder Filter ist eine Schnittfamilie^[1].

Eine k-Schnittfamile bezeichnet eine Schnittfamile in der alle Elemente die Mächtigkeit k haben, für maximale Mächtigkeiten solcher Familie macht der Satz von Erdös-Ko-Rado eine Aussage.

Nach dem Satz von Kleitman hat die Vereinigung von m Schnittfamilien $\bar F = \bigcup_{i=1}^n F_i$ höchstens $\bar F \leqslant 2^n - 2^{n-m}$ Teilmengen^[2].

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

1. ↑ Stasys Jukna Extremal Combinatorics S. 90 Springer, Berlin 2001, ISBN 3-540-66313-4
2. ↑ Stasys Jukna Extremal Combinatorics S. 91 Springer, Berlin 2001, ISBN 3-540-66313-4