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.

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.

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