Lemma von Kleitman

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.[1][2][3]

Das Lemma lässt sich angeben wie folgt:[1][2][3]

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.[A 1]
Dann gilt die folgende Ungleichung:
.[A 2]

Das Lemma zieht eine Reihe von Folgerungen nach sich. Dazu gehören nicht zuletzt die folgenden:[1][2][3]

(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 .[A 3] Diese obere Schranke ist für alle natürlichen Zahlen und mit die bestmögliche.

Verwandter Satz

[Bearbeiten | Quelltext bearbeiten]

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:[4][3]

Ist eine natürliche Zahl und sind verschiedene Mengen gegeben, so gibt es dazu stets mindestens verschiedene Differenzmengen .

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. a b c Ian Anderson: Combinatorics of Finite Sets. 1987, S. 87 ff.
  2. a b c Béla Bollobás: Combinatorics. 1986, S. 143 ff.
  3. a b c d Konrad Engel: Sperner Theory. 1997, S. 265 ff.
  4. J. Marica, J. Schönheim: Differences of sets and a problem of Graham. In: Canad. Math. Bull. 12, S. 635–637
  1. Selbstverständlich betrachtet man hier – wie üblich!– als versehen mit der Inklusionsrelation.
  2. ist die Anzahlfunktion.
  3. Ein Mengensystem mit der genannten Durchschnittseigenschaft bezeichnet man in der englischsprachigen mathematischen Fachliteratur als intersecting family.