Schnittfamilie

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

Definition

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

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

Bemerkungen

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

Jeder Filter i​st eine Schnittfamilie.[1]

Eine ${\displaystyle k}$-Schnittfamilie bezeichnet eine Schnittfamilie, in der alle Elemente die Mächtigkeit ${\displaystyle 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 ${\displaystyle m}$ Schnittfamilien ${\displaystyle {\bar {F}}=\bigcup _{i=1}^{m}F_{i}}$ höchstens ${\displaystyle |{\bar {F}}|\leq 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. Springer, Berlin 2001, ISBN 3-540-66313-4, S. 90.
2. Stasys Jukna: Extremal Combinatorics. Springer, Berlin 2001, ISBN 3-540-66313-4, S. 91.