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

Definition

Bearbeiten

Eine Mengenfamilie   wird als Schnittfamilie bezeichnet, wenn folgende Eigenschaft erfüllt ist:

Für alle   gilt  .

Bemerkungen

Bearbeiten

Die maximale Mächtigkeit einer Schnittfamilie   einer endlichen Menge   der Mächtigkeit   ist  .

Jeder Filter ist eine Schnittfamilie.[1]

Eine  -Schnittfamilie bezeichnet eine Schnittfamilie, in der alle Elemente die Mächtigkeit   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   Schnittfamilien   höchstens   Teilmengen.[2]

Einzelnachweise

Bearbeiten
  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.