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 𝒫(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\ne \varnothing$.

Bemerkungen

Die maximale Mächtigkeit einer Schnittfamilie $F$ einer endlichen Menge $N$ der Mächtigkeit $n$ ist $|F|\le 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 $\overline{F}=\bigcup _{i=1}^m{F}_i$ höchstens $|\overline{F}|\le 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.