Quelltext der Seite Schnittfamilie

Eine '''Schnittfamilie''' einer Menge <math>N</math> bezeichnet in der Mathematik eine [[Familie (Mathematik)|Familie]] von Teilmengen von <math>N</math>, bei der je zwei ihrer Elemente einen nichtleeren Schnitt haben.

== Definition ==
Eine [[Mengenfamilie]] <math>F \subseteq \mathcal{P}(N)</math> wird als Schnittfamilie bezeichnet, wenn folgende Eigenschaft erfüllt ist:

:Für alle <math>A_i,A_j \in F</math> gilt <math>A_i \cap A_j \neq  \varnothing</math>.

== Bemerkungen ==
Die maximale Mächtigkeit einer Schnittfamilie <math>F </math> einer endlichen Menge <math>N</math> der Mächtigkeit <math>n</math> ist <math> |F| \leq 2^{n-1} </math>.

Jeder [[Filter (Mathematik)|Filter]] ist eine Schnittfamilie.<ref>[[Stasys Jukna]]: ''Extremal Combinatorics.'' Springer, Berlin 2001, ISBN 3-540-66313-4, S. 90.</ref>

Eine <math>k</math>-Schnittfamilie bezeichnet eine Schnittfamilie, in der alle Elemente die Mächtigkeit <math>k</math> 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 <math>m</math> Schnittfamilien <math>\bar F = \bigcup_{i=1}^m F_i</math> höchstens <math>|\bar F| \leq 2^n - 2^{n-m}</math> Teilmengen.<ref>[[Stasys Jukna]]: ''Extremal Combinatorics.'' Springer, Berlin 2001, ISBN 3-540-66313-4, S. 91.</ref>

== 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 ==
<references />

[[Kategorie:Mengenlehre]]