Schnittfamilie

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

Definitition

Eine Familie wird als Schnittfamilie $F$ bezeichnet, wenn folgede 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$ hat eine obere Grenze:

$|F|\leqslant 2^{n-1}$.

Jeder Filter ist eine Schnittfamilie.

Eine k-Schnittfamile bezeichnet eine Schnittfamile in der alle Elemente die Mächtigkeit k haben.

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 Junka Extremal Combinatorics Springer, Berlin 2001, ISBN 3-540-66313-4