Lemma von Kleitman

Der Lemma von Kleitman, englisch Kleitman's lemma, 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 (englisch Ahlswede–Daykin inequality), 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 ${\mathcal {D}}\subseteq {\mathcal {P}}(X)$ und ${\mathcal {U}}\subseteq {\mathcal {P}}(X)$.

Dabei soll gelten, dass innerhalb ${\mathcal {P}}(X)$ einerseits ${\mathcal {D}}$ ein Ideal sei und andererseits ${\mathcal {U}}$ ein Filter.

Dann gilt die folgende Ungleichung:

$|{\mathcal {D}}\cap {\mathcal {U}}|\leq {\frac {|{\mathcal {D}}|\cdot |{\mathcal {U}}|}{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 ${\mathcal {A}}\subseteq {\mathcal {P}}(X)$ gegeben, welches zudem die Eigenschaft haben soll, dass für $A,B\in {\mathcal {A}}$ stets die Relationen $A\cap B\neq \emptyset \,,\,A\cup B\neq X$ erfüllt seien, so gilt die Ungleichung $|{\mathcal {A}}|\leq 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 ${\mathcal {A}}_{1},\ldots ,{\mathcal {A}}_{k}\subseteq {\mathcal {P}}(X)\,(k\in \mathbb {N} )$ gegeben derart, dass für $j=1,\ldots ,k$ und $A,B\in {\mathcal {A}}_{j}$ stets die Relation $A\cap B\neq \emptyset$ erfüllt ist, so gilt für die Gesamtheit all dieser Teilmengen die Ungleichung $|\bigcup _{j=1,\ldots ,k}{{\mathcal {A}}_{j}}|\leq \left(2^{n}-2^{n-k}\right)$. Diese obere Schranke ist für alle natürlichen Zahlen $n$ und $k$ mit $1\leq k\leq 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},\ldots ,A_{m}$ gegeben, so gibt es dazu stets mindestens $m$ verschiedene Differenzmengen ${A_{i}\setminus A_{j}}\,(i,j=1,\ldots ,m)$ .

Literatur

• Rudolf Ahlswede, David E. Daykin: An inequality for the weights of two families of sets, their unions and intersections. In: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete. Band 43, 1978, S. 183–185 (MR0491189). 
• Ian Anderson: Combinatorics of Finite Sets. Clarendon Press, Oxford 1987, ISBN 0-19-853367-5 (MR0892525). 
• Béla Bollobás: Combinatorics. Set systems, Hypergraphs, Families of Vectors and Combinatorial Probability. Cambridge University Press, Cambridge, London, New York, New Rochelle, Melbourne, Sydney 1986, ISBN 0-521-33703-8 (MR0866142). 
• Konrad Engel: Sperner Theory (= Encyclopedia of Mathematics and its Applications. Band 65). Cambridge University Press, Cambridge u. a. 1997, ISBN 0-521-45206-6 (MR1429390). 
• Daniel J. Kleitman: Families of non-disjoint subsets. In: Journal of Combinatorial Theory. Band 1, 1966, S. 153–155 (MR0193020). 
• J. Marica, J. Schönheim: Differences of sets and a problem of Graham. In: Canadian Mathematical Bulletin. Band 12, 1969, S. 635–637 (MR0249388).