Schnittfamilie

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

Definition

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

Für alle $A_{i},A_{j}\in F$ gilt $A_{i}\cap A_{j}\neq \varnothing$.

Bemerkungen

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

Jeder Filter ist eine Schnittfamilie.

Eine $k$-Schnittfamilie bezeichnet eine Schnittfamilie, in der alle Elemente die Mächtigkeit $k$ 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 $m$ Schnittfamilien ${\bar {F}}=\bigcup _{i=1}^{m}F_{i}$ höchstens $|{\bar {F}}|\leq 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.