Beweisarchiv: Kombinatorik: Eine verallgemeinerte LYM-Ungleichung

Aus Wikibooks
Wechseln zu: Navigation, Suche

Beweisarchiv: Kombinatorik

Eine verallgemeinerte LYM-Ungleichung

In der Spernertheorie, einem Teilgebiete der Kombinatorik, besteht einer der üblichen Ansätze zur Herleitung des Satzes von Sperner darin, zunächst die Lubell-Yamamoto-Meshalkin-Ungleichung - auch kurz LYM-Ungleichung genannt[1] - zu zeigen und daraus dann den spernerschen Satz zu folgern.

Wie sich zeigt, ist bei diesem Ansatz wesentlich, dass bei einer endlichen Potenzmenge     über einer endlichen Grundmenge     die Automorphismengruppe     mit der symmetrischen Gruppe   über   identifiziert werden kann:

Denn jeder solcher Automorphismus zeichnet sich dadurch aus, dass er die Inklusionsordnung der Potenzmenge strikt erhält, weswegen er stets mit einer Permutation der Atome des booleschen Verbandes     - also der einelementigen Teilmengen von     ! - zusammengehört, welche ihn wegen der Verbandseigenschaften von     völlig bestimmt.

Daher ist jeder der zugehörigen Orbits

nichts weiter sind als eine der Mächtigkeitsklassen

 ,

da nämlich für     die Menge     nichts anderes ist als die Menge der   -Bilder von     unter der Permutation .

Geht man nun von     zu beliebigen endlichen Gruppen und allgemeinen Gruppenoperationen über, so erhält man eine Verallgemeinerung der LYM-Ungleichung, welche sogar ganz unabhängig von den Ordnungsbetrachtungen innerhalb der endlichen Potenzmengen Gültigkeit hat.[2]

Formulierung der Verallgemeinerung[Bearbeiten]

Gegeben sei eine endliche (multiplikativ geschriebene) Gruppe mit neutralem Element .
sei eine endliche Menge und hierauf operiere vermöge der Gruppenoperation
.
Weiter seien eine Teilmenge gegeben und eine endliche Familie von Elementen von , wobei eine endliche nichtleere Indexmenge sein möge.
Dabei sei für
  .
Dann gilt  :
.

Beweis[Bearbeiten]

Schritt 1[Bearbeiten]

Wir setzen

    .

Damit gilt:

(1)

Wir wenden (1) an, ausgehend von einer gegebenen Zahlenfamilie , auf die reellwertige Funktion

an.

Aus Disjunktheitsgründen erhalten wir zunächst[3]

(2)

und daraus unmittelbar die Ungleichung

(3)   .

Aus (3) gelangt man sogleich zu der Ungleichung

(4)   .

Mit (4) jedoch ergibt sich sofort die Behauptung, wenn noch für jeden Index die folgende Identität (5) gezeigt wird:

(5)   .

Schritt 2[Bearbeiten]

Zum Beweis von (5) sei irgendeiner der Indizes. Der Vereinfachung halber sei gesetzt.

Es ist dann

(6)   .

Nun lässt sich zu jedem ein Gruppenelement als fest vorgegeben annehmen, welches die Gleichung erfüllt .

Damit lässt sich beweisen - siehe Schritt 3 unten! - dass die Gleichung

(7)

besteht.

Und dies reicht aus zum Beweis von (5):

Denn man berücksichtigt erst einmal die Tatsache, dass jede Translation eine Bijektion ist, weswegen man mit (7) zunächst

(8)

hat. Dann wird weiter berücksichtigt, dass in die bisherigen Überlegungen keine speziellen Eigenschaften der Teilmenge eingeflossen sind, dass also (8) für jedes und dann inbesondere auch für richtig ist. Also folgt sogleich

(9)   .

Verknüpft man nun (8) und (9), so hat man (5).

Schritt 3[Bearbeiten]

Zum Nachweis von (7) sind die Inklusion von links nach rechts und umgekehrt die Inklusion von rechts nach links zu zeigen.

Zunächst wird erstere gezeigt. Dazu sei .

Es gilt dann

(10)

und folglich

(11)   .

Zum Nachweis der umgekehrten Inklusion sei und dafür die Gleichung erfüllt.

Dann ist wie stets

(12)

und hierbei gilt

(13) .

Also haben wir

(14)   .

(11) und (14) zusammen ergeben (7) .

Korollar: Die klassische LYM-Ungleichung[Bearbeiten]

Ist unter den oben beschriebenen Gegebenheiten die Sitution derart, dass jede der Indexmengen     aus höchstens einem einzigen Index besteht, so gilt insbesondere:
.

Direkte Herleitung der klassischen LYM-Ungleichung aus der verallgemeinerten LYM-Ungleichung[Bearbeiten]

Die verallgemeinerte LYM-Ungleichung umfasst eine Anzahl von Ungleichungen der Spernertheorie und insbesondere auch die klassische Lubell-Yamamoto-Meshalkin-Ungleichung und .[2]

Zur Herleitung der klassischen LYM-Ungleichung aus der verallgemeinerten LYM-Ungleichung betrachtet man irgend eine endliche Menge     . Ohne Beschränkung der Allgemeinheit kann angenommen werden, dass     für     ist.

Man wendet die verallgemeinerte LYM-Ungleichung an für den Fall, dass

und

und dann noch

ist .

Hierbei wird, wie oben dargelegt, die Automorphismengruppe mit der symmetrischen Gruppe identifiziert.

Wie oben erwähnt, hat man als Operation

dabei

vorliegen.

Man legt nun für das obige     eine Antikette der Potenzmenge     zugrunde, also ein Mengensystem     von Teilmengen von , welches so beschaffen ist, dass von diesen Teilmengen keine zwei verschiedene einander umfassen.

Bedeutsam ist nun, dass man stets folgende Kette von Teilmengen innerhalb     hat:

sowie für  

  .

Damit hat man für   :

und zudem

  .

Weiter von Bedeutung ist die Klärung der Frage, wie groß für eine Permutation     das ihr zugehörige     sein kann. Dies ist jedoch unmittelbar einsichtig:

Denn da     Antikette ist, kann es niemals vorkommen, dass für zwei unterschiedliche     - etwa     -     gilt, weil nämlich die Inklusion     stets die Inklusion     nach sich zieht (und umgekehrt).

Das heißt jedoch, dass für     durchgängig

gilt!

Bezeichnet man nun noch für     mit     die Anzahl der in     vorkommenden Mengen, welche aus exakt     Elementen bestehen, so hat man:

  .

Legt man dann noch die konstante Zahlenfamilie

 

zugrunde, so folgt aus dem Korollar unmittelbar die LYM-Ungleichung.

Weitere Anwendung: Ein allgemeiner Charakterisierungssatz zur LYM-Eigenschaft[Bearbeiten]

Die oben dargestellte Verallgemeinerung der LYM-Ungleichung kann verstanden werden als ein Teilschritt hin zu einer allgemeinen Charakterisierung der LYM-Eigenschaft, welche diese in Zusammenhang bringt mit dem Konzept der Operation von Gruppen auf Mengen.[4][5]

Hierbei betrachtet man eine endliche teilweise geordnete Menge

mit der Ordnungsrelation

.

Dabei sei

die Menge der verschiedenen Orbits

,

welche durch die Operation

der Automorphismengruppe auf entstehen.

Weiter sei

die Menge der Ketten innerhalb , also die Menge aller Teilmengen von mit der Eigenschaft, dass für je zwei darin enthaltene Elemente stets die Relation oder die Relation erfüllt ist.

Schließlich sei

die Menge der Antiketten innerhalb , also die Menge aller Teilmengen von mit der Eigenschaft, dass für je zwei darin enthaltene Elemente niemals die Relation erfüllt ist.[6]

Formulierung des allgemeinen Charakterisierungssatzes[Bearbeiten]

Unter den oben genannten Voraussetzungen gilt:

(A) Jeder der Orbits ist eine Antikette von :
.
(B) Die folgenden vier Bedingungen sind gleichwertig:
(B1)
Für gilt stets
.
(B2)
Jeder der Orbits ist eine maximale Antikette, wird also von keiner anderen Antikette von echt umfasst.
(B3)
In existiert eine Kette, welche zugleich ein Repräsentantensystem der durch die Orbitmenge gegebenen Partition
darstellt.
(B4)
Für jede Funktion , bei der sämtliche Restriktionen konstante Funktionen sind, gilt
.

Beweis des Charakterisierungssatzes[Bearbeiten]

Ad (A)[Bearbeiten]

Die Annahme, es würde für und

(1) [7]

gelten, führt mittels Iteration zu der Ungleichungskette

(2) .

Da endlich ist, jede solche Kette jedoch unendlich, kann (2) nicht gelten und damit ebenso wenig (1).

Folglich ist jeder -Orbit eine Antikette von .[8]

Ad (B)[Bearbeiten]

Der Beweis wird in einem Ringschluss geführt. Dazu sei .

(B1) → (B2)[Bearbeiten]

Wenn eine Teilmenge einen Orbit echt umfasst, so gilt

(3)

für mindestens ein zu einem Orbit .

Also folgt

(4) .

Durch (4) ist die Ungleichung von (B1) verletzt, weswegen im Falle der Gültigkeit von (B1) keine solches noch Antikette von sein kann.

(B2) → (B3)[Bearbeiten]
Schritt 1[Bearbeiten]

Man definiert zunächst eine Hilfsfunktion , die sich infolge der Tatsache ergibt, dass beliebiges stets mindestens ein  

- nämlich   -

existiert, so dass

(4)

erfüllt ist.[9]

Also ist vermöge

(5)

eine sinnvoll erklärte Funktion gegeben.[10][11]

Nun ist die Bildmenge eine nichtleere Teilmenge der natürlichen Zahlen und daher kann man ihre Mächtigkeit abschätzen wie folgt:

(6) .

Gemäß (5) ergibt sich aus (6) sofort

(7) .

An dieser Stelle ist die wesentliche Tatsache zu berücksichtigten, dass eine Kette und eine Antikette von stets allerhöchstens ein einziges Element gemeinsam haben.

Deswegen ist vermöge (A) für stets die Abschätzung

(8)

gegeben.

Da andererseits die Orbits eine Partition von bilden, zieht (8) durchgängig die wichtige Beziehung

(9)

nach sich.

Verbindet man (7) und (9), so hat man die Ungleichungskette

(10) .
Schritt 2[Bearbeiten]

Es genügt zum Schluss auf (B3) zu zeigen, dass bei Voraussetzung von (B2) stets die Identität

(11)

besteht.

Denn:

Aus (11) ergibt sich dann in Verbindung mit (10) zunächst

(12) .

D mit auch endlich ist , zieht (12) in Verbindung nach sich, dass für mindestens ein in (9) und dann auch in (8) das Gleichheitszeichen gilt.

Das aber heißt:

Es gibt in eine Kette, welche zugleich ein Repräsentantensystem für die Orbitmenge darstellt.

Schritt 3[Bearbeiten]

Zur Vollendung des Beweises von (B2) → (B3) bleibt also die Identität (11) zu zeigen.

Dazu sei

(13) und .

ist offenbar eine Antikette von und zudem nicht die leere Menge.

Man wählt nun irgendein .

Jetzt wird bedeutsam, dass jedes und ebenso die zugehörige inverse Abbildung die Ordnungsstruktur von streng erhalten.

Das bedeutet:

Es entsprechen unter diejenigen Ketten, in denen das Maximum ist, umkehrbar eindeutig denjenigen Ketten, in denen das Maximum ist.

Dies zieht die Gleichung

(14)

nach sich.

(14) wiederum bedeutet, dass der Orbit, dem angehört, etwa , ganz in enthalten ist:

(15) .

Nun kommt die vorausgesetzte Bedingung (B2) zur Wirkung. Derzufolge kann in (15) nicht die strenge Inklusion gelten.

Man hat also sogar die Identität

(16) .

Ganz gleichartige Überlegungen lassen sich jedoch für alle anstellen. Folglich gilt insgesamt

(17) .

Nun ist auch eine Partition von und zwei Partitionen einer Menge können einander niemals echt umfassen.

Daher verschärft sich (17) zu der Identität

(18) .

Mit (18) jedoch gilt dann auch die Identität

(19) .

Die Identität (19) wiederum impliziert die Identität (11) und diese war zu zeigen.

(B3) → (B4)[Bearbeiten]

Es sei eine reellwertige Funktion, bei der sämtliche Restriktionen konstante Funktionen sind. Für ein solches ist zum Nachweis der Identität (B4) in zwei Schritten zu beweisen, dass dort sowohl von links nach rechts als auch von rechts nach links die entsprechenden Ungleichungen gelten.

Schritt 1[Bearbeiten]

Der erste Schritt ist sehr einfach. Denn es gilt (A) und daher ist selbstverständlich

(20) .
Schritt 2[Bearbeiten]

Also bleibt zum Nachweis von (B4) allein die zu (20) duale Ungleichung herzuleiten.

Dazu sei eine beliebige Antikette . Hierfür ist die Ungleichung

(21)

zu zeigen.

Dies geschieht durch Anwendung des Korollars zur verallgemeinerten LYM-Ungleichung.

Dazu wird zunächst einbezogen, dass gemäß Voraussetzung in eine Kette

(22)

enthalten ist.

Es ist damit für stets

(23)

gültig und daher für jedes aufgrund der Beschaffenheit von in Verbindung mit (22) und (23) durchgängig

(24) .

Wegen der Partitionseigenschaften von folgt nun aus (24) sogleich

(25) .

An dieser Stelle ist zu berücksichtigen, dass für jeden Automorphismus mit auch stets eine Kette von ist.

Folglich gilt wegen der Antiketteneigenschaft von stets

(26) .

Es kann also immer nur höchstens einen einzigen Index geben mit .

Somit folgt schließlich aus (25) und (26) durch Anwendung des Korollars zur verallgemeinerten LYM-Ungleichung die Ungleichung (21) und damit (B4).

(B4) → (B1)[Bearbeiten]

Vermöge

(27)

ist eine reelwertige Funktion auf erklärt, welche die in (B4) genannte Eigenschaft hat.

Denn es ist offenbar für und durchgängig

(28) .

Folglich ist für stets

(29) .

Damit aber erhält man unter der Voraussetzung von (B4) für jede Antikette

(30) .

Mit (30) jedoch hat man (B1) .

Nachbetrachtung und Beispiele[Bearbeiten]

Aus dem allgemeine Charakterisierungssatz lässt sich ablesen, wie die LYM-Eigenschaft aus einem gruppentheoretischen Gesichtswinkel gedeutet werden kann. Sie bedeutet, wie man insbesondere an (B2) und (B3) abliest, dass die Automorhismengruppe in besonders einfacher Art und Weise auf operiert.

An (B4) - mit - wiederum sieht man, dass für ein solches stets das Analogon zum Satz von Sperner gilt:[12]

Herausragende Beispiele solcher sind neben den endlichen Potenzmengen vor allem folgende:[13]

  • die endlichen Ketten
  • die endlichen Antiketten
  • die Unterraumverbände endlichdimensionaler Vektorräume über endlichen Körpern

Quellen und Hintergrundliteratur[Bearbeiten]

  • Ian Anderson: Combinatorics of Finite Sets. Clarendon Press, Oxford 1987, ISBN 0-19-853367-5. MR0892525
  • Konrad Engel: Sperner Theory. 65, Cambridge University Press, Cambridge (u. a.) 1997, ISBN 0-521-45206-6. MR1429390
  • D. Lubell: A short proof of Sperner's lemma. Journal of Combinatorial Theory, Vol. 1, 2 (1966): 299. DOI:10.1016/S0021-9800(66)80035-2, MR0194348
  • L.D. Meshalkin: Generalization of Sperner's theorem on the number of subsets of a finite set. Theory of Probability and its Applications, Vol. 8, 2 (1963): 203–204. DOI:10.1137/1108023, MR0150049
  • Kurt Meyberg: Algebra. Teil 1. Carl Hanser Verlag, München, Wien 1975, ISBN 3-446-11965-5. [1]
  • Hans-Josef Scholz: Über die Kombinatorik der endlichen Potenzmengen im Zusammenhang mit dem Satz von Sperner. Dissertation, Universität Düsseldorf (1987).
  • Emanuel Sperner: Ein Satz über Untermengen einer endlichen Menge. Math. Z. 27 (1928): 544–548. MR1544925
  • Koichi Yamamoto: Logarithmic order of free distributive lattice. Journal of the Mathematical Society of Japan, Vol. 6 (1954): 343–353. MR0067086.

Einzelnachweise und Fußnoten[Bearbeiten]

  1. Die Ungleichung wird so bezeichnet, da in den Arbeiten von Lubell (1966), Yamamoto (1954) und Meshalkin (1963) zum ersten Mal - soweit bekannt - der Satz von Sperner auf sie zurückgeführt wurde. In der englischsprachigen Fachliteratur bezeichnet man sie entsprechend als LYM inequality.
  2. 2,0 2,1 Hans-Josef Scholz: Über die Kombinatorik .... 1987, S. 30 ff.
  3. Hier ist zu beachten, dass man in der Kombinatorik bei endlichen Mengen und einer darauf definierten reellwertigen Funktion oft abkürzend schreibt oder auch oder Ähnliches, wenn man die Summe meint. Hier wird die erstgenannte Abkürzung benutzt und nicht die zweitgenannte, um Konfusionen mit der Bildmengenbezeichnung zu vermeiden.
  4. Hans-Josef Scholz: Über die Kombinatorik .... 1987, S. 11 ff, S. 30 ff.
  5. Ein anderer (jedoch in vielfacher Weise verwandter) Weg, die LYM-Eigenschaft in einem allgemeinen Rahmen zu studieren, wird in der Theorie der teilweise geordneten Mengen mit Rangfunktion (engl. ranked posets) durchgeführt. Diese inzwischen sehr umfassend entwickelte Theorie ist ausführlich in den Monographien von Ian Anderson (Combinatorics of Finite Sets, Oxford 1987) und Konrad Engel (Sperner Theory, Cambridge 1997) dargestellt.
  6. Wie üblich schreibt man für bei zwei Elemente für die verknüpfte Relation .
  7. In diesem Teil zum allgemeinen Charakterisierungssatz beginnen die Randziffern für die einzelnen Beweisschritte neu mit (1) .
  8. Dieser einfache Beweis stammt von Egbert Harzheim.
  9. In jeder endlichen Kette gibt es stets das eindeutig bestimmte Maximum, welches in der gegebenen Ordnung mit jedem anderen Element der Kette vergleichbar und dabei niemals als ein solches ist.
  10. Das hintere Maximum wird innerhalb der natürlichen Zahlen gebildet. Anschaulich gesprochen handelt es sich um die Mächtigkeit einer längsten Kette, die in endet. Dass eine solche längste Kette stets existiert, ergibt sich aus der Endlichkeit von .
  11. In Kombinatorik und Ordnungstheorie wird die Funktion - meist unter Voraussetzung gewisser Regularitätsannahmen - manchmal auch als Höhenfunktion oder Rangfunktion bezeichnet.
  12. Hans-Josef Scholz: Über die Kombinatorik .... 1987, S. 16
  13. Hans-Josef Scholz: Über die Kombinatorik .... 1987, S. 15-16