Lemma von Kleitman

Der Lemma von Kleitman, Vorlage:EnS, ist einer der Lehrsätze des mathematischen Teilgebiets der Kombinatorik. Es geht auf eine Arbeit von Daniel J. Kleitman aus dem Jahre 1966 zurück und behandelt eine Größenabschätzung für gewisse Teilmengensysteme innerhalb einer endlichen Potenzmenge. Das Lemma steht in enger Beziehung zu der Ungleichung von Ahlswede-Daykin (Vorlage:EnS), mit der es sich leicht herleiten lässt.

Formulierung

Das Lemma lässt sich angeben wie folgt:

Gegeben seien eine natürliche Zahl $n$ sowie eine endliche Menge $X$ mit $n$ Elementen und dazu zwei Teilmengensysteme $𝒟\subseteq 𝒫(X)$ und $𝒰\subseteq 𝒫(X)$.

Dabei soll gelten, dass innerhalb $𝒫(X)$ einerseits $𝒟$ ein Ideal sei und andererseits $𝒰$ ein Filter.

Dann gilt die folgende Ungleichung:

$|𝒟\cap 𝒰|\le \frac{|𝒟|\cdot |𝒰|}{2^n}$ .

Folgerungen

Das Lemma zieht eine Reihe von Folgerungen nach sich. Dazu gehören nicht zuletzt die folgenden:

(i) Ist (unter den obigen allgemeinen Voraussetzungen) ein Teilmengensystem $𝒜\subseteq 𝒫(X)$ gegeben, welches zudem die Eigenschaft haben soll, dass für $A,B\in 𝒜$ stets die Relationen $A\cap B\ne \mathrm{\varnothing },A\cup B\ne X$ erfüllt seien, so gilt die Ungleichung $|𝒜|\le 2^{n-2}$. Diese obere Schranke ist für jede natürliche Zahl $n$ die bestmögliche.

(ii) Sind (unter den obigen allgemeinen Voraussetzungen) endlich viele Teilmengensysteme ${𝒜}_1,\dots ,{𝒜}_k\subseteq 𝒫(X)(k\in \mathbb{N})$ gegeben derart, dass für $j=1,\dots ,k$ und $A,B\in {𝒜}_j$ stets die Relation $A\cap B\ne \mathrm{\varnothing }$ erfüllt ist, so gilt für die Gesamtheit all dieser Teilmengen die Ungleichung $|\bigcup _{j=1,\dots ,k}{𝒜}_j|\le (2^n-2^{n-k})$. Diese obere Schranke ist für alle natürlichen Zahlen $n$ und $k$ mit $1\le k\le n$ die bestmögliche.

Verwandter Satz

Verwandt mit dem Kleitman'schen Lemma ist ein Satz, der im Jahre 1969 von John G. Marica und Johanan Schönheim vorgelegt wurde und die folgende elementare Aussage macht:

Ist $m$ eine natürliche Zahl und sind verschiedene Mengen $A_1,\dots ,A_m$ gegeben, so gibt es dazu stets mindestens $m$ verschiedene Differenzmengen $A_i\setminus A_j(i,j=1,\dots ,m)$ .

Literatur

• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur