Der Lemma von Kleitman, , 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 (), mit der es sich leicht herleiten lässt.Ian Anderson: Combinatorics of Finite Sets. 1987, S. 87 ff.Béla Bollobás: Combinatorics. 1986, S. 143 ff.Konrad Engel: Sperner Theory. 1997, S. 265 ff.
Formulierung Das Lemma lässt sich angeben wie folgt: Gegeben seien eine natürliche Zahl sowie eine endliche Menge mit Elementen und dazu zwei Teilmengensysteme und . Dabei soll gelten, dass innerhalb einerseits ein Ideal sei und andererseits ein Filter.Selbstverständlich betrachtet man hier – wie üblich!– als versehen mit der Inklusionsrelation.
Dann gilt die folgende Ungleichung:
. ist die Anzahlfunktion.
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 gegeben, welches zudem die Eigenschaft haben soll, dass für stets die Relationen erfüllt seien, so gilt die Ungleichung . Diese obere Schranke ist für jede natürliche Zahl die bestmögliche.
(ii) Sind (unter den obigen allgemeinen Voraussetzungen) endlich viele Teilmengensysteme gegeben derart, dass für und stets die Relation erfüllt ist, so gilt für die Gesamtheit all dieser Teilmengen die Ungleichung .Ein Mengensystem mit der genannten Durchschnittseigenschaft bezeichnet man in der englischsprachigen mathematischen Fachliteratur als intersecting family. Diese obere Schranke ist für alle natürlichen Zahlen und mit 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:J. Marica, J. Schönheim: Differences of sets and a problem of Graham. In: Canad. Math. Bull. 12, S. 635–637 Ist eine natürliche Zahl und sind verschiedene Mengen gegeben, so gibt es dazu stets mindestens verschiedene Differenzmengen .
Literatur
Einzelnachweise
Anmerkungen
Kleitman, Lemma von