Beweisarchiv: Kombinatorik: Eine verallgemeinerte LYM-Ungleichung

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 - zu zeigen und daraus dann den spernerschen Satz zu folgern.

Wie sich zeigt, ist bei diesem Ansatz wesentlich, dass bei einer endlichen Potenzmenge   $2^{M}$   über einer endlichen Grundmenge   $M$   die Automorphismengruppe   $\operatorname {Aut} (2^{M})$   mit der symmetrischen Gruppe   $S_{M}$ über $M$   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   $2^{M}$   - also der einelementigen Teilmengen von   $M$   ! - zusammengehört, welche ihn wegen der Verbandseigenschaften von   $2^{M}$   völlig bestimmt.

Daher ist jeder der zugehörigen Orbits

$\operatorname {Aut} (2^{M})\cdot X=S_{M}\cdot X=\{g(X):g\in S_{M}\}\;(X\subseteq M)$

nichts weiter sind als eine der Mächtigkeitsklassen

${M \choose i}\subseteq 2^{M}\;(i=0,\ldots ,|M|)$  ,

da nämlich für   $X\subseteq M$   die Menge   $g(X)$   nichts anderes ist als die Menge der   $g$-Bilder von   $X$   unter der Permutation $g$.

Geht man nun von   $\operatorname {Aut} (2^{M})$   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.

Formulierung der Verallgemeinerung

Gegeben sei eine endliche (multiplikativ geschriebene) Gruppe $(G,\cdot )$ mit neutralem Element $e$.

$S$ sei eine endliche Menge und hierauf operiere $(G,\cdot )$ vermöge der Gruppenoperation

$G\times S\to S$

$(g,s)\mapsto g\cdot s$.

Weiter seien eine Teilmenge $A\subseteq S$ gegeben und eine endliche Familie $(c_{i})_{i\in I}$ von Elementen von $S$, wobei $I$ eine endliche nichtleere Indexmenge sein möge.

Dabei sei für $g\in G$

$I_{g}=\{i\in I:{g\cdot c_{i}}\in A\}$   .

Dann gilt  :

$\sum _{i\in I}{\frac {|{G\cdot c_{i}}\cap {A}|}{|{G\cdot c_{i}}|}}\cdot w_{i}\leq \max _{g\in G}{\sum _{i\in I_{g}}{w_{i}}}$.

Beweis

Schritt 1

Wir setzen

$G^{i}=\{g\in G:{g\cdot c_{i}}\in A\}$   $(\forall i\in I)$   .

Damit gilt:

(1) $\bigcup _{i\in I}{G^{i}\times \{i\}}=\bigcup _{g\in G}{\{g\}\times I_{g}}$

Wir wenden (1) an, ausgehend von einer gegebenen Zahlenfamilie $(w_{i})_{i\in I}$, auf die reellwertige Funktion

$v\colon G\times I\to \mathbb {R} \;,\;v(g,i)=w_{i}$

an.

Aus Disjunktheitsgründen erhalten wir zunächst

(2) $\sum _{i\in I}{v[G^{i}\times \{i\}]}=\sum _{g\in G}{v[\{g\}\times I_{g}]}$

und daraus unmittelbar die Ungleichung

(3) $\sum _{i\in I}{v[G^{i}\times \{i\}]}\leq |G|\max _{g\in G}{\;v[\{g\}\times I_{g}]}$   .

Aus (3) gelangt man sogleich zu der Ungleichung

(4) $\sum _{i\in I}{|G^{i}|\cdot w_{i}}\leq |G|\max _{g\in G}{\;\sum _{i\in I_{g}}{w_{i}}}$   .

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

(5) $|G^{i}|={\frac {|G|\cdot |{G\cdot c_{i}}\cap {A}|}{|{G\cdot c_{i}}|}}$   .

Schritt 2

Zum Beweis von (5) sei $j$ irgendeiner der Indizes. Der Vereinfachung halber sei $c:=c_{j}$ gesetzt.

Es ist dann

(6) $|G^{j}|=\sum _{a\in A}{|\{g\in G\colon g\cdot c=a\}|}=\sum _{a\in (G\cdot c\;\cap \;A)}{|\{g\in G\colon g\cdot c=a\}|}$   .

Nun lässt sich zu jedem $a\in (G\cdot c\;\cap \;A)$ ein Gruppenelement $h\in G$ als fest vorgegeben annehmen, welches die Gleichung $h\cdot c=a$ erfüllt .

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

(7) $hG_{c}=\{g\in G\colon g\cdot c=a\}$

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) $|G^{j}|=|G_{c}||G\cdot c\;\cap \;A|$

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

(9) $|G|=|G_{c}||G\cdot c|$   .

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

Schritt 3

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 $g^{'}\in G_{c}$.

Es gilt dann

(10) $(hg^{'})\cdot c=h\cdot (g^{'}\cdot c)=h\cdot c=a$

und folglich

(11) $hG_{c}\subseteq \{g\in G\colon g\cdot c=a\}$   .

Zum Nachweis der umgekehrten Inklusion sei $g\in G$ und dafür die Gleichung $g\cdot c=a$ erfüllt.

Dann ist wie stets

(12) $g=h(h^{-1}g)$

und hierbei gilt

(13) $(h^{-1}g)\cdot c=h^{-1}\cdot (g\cdot c)=h^{-1}\cdot a=h^{-1}\cdot (h\cdot c)=(h^{-1}h)\cdot c=e\cdot c=c$ .

Also haben wir

(14) $\{g\in G\colon g\cdot c=a\}\subseteq hG_{c}$   .

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

Korollar: Die klassische LYM-Ungleichung

Ist unter den oben beschriebenen Gegebenheiten die Sitution derart, dass jede der Indexmengen   $I_{g}\;(g\in G)$   aus höchstens einem einzigen Index besteht, so gilt insbesondere:

$\sum _{i\in I}{\frac {|{G\cdot c_{i}}\cap {A}|}{|{G\cdot c_{i}}|}}\cdot w_{i}\leq \max _{i\in I}\;{w_{i}}$.

Direkte Herleitung der klassischen LYM-Ungleichung aus der verallgemeinerten LYM-Ungleichung

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

Zur Herleitung der klassischen LYM-Ungleichung aus der verallgemeinerten LYM-Ungleichung betrachtet man irgend eine endliche Menge   $M$   . Ohne Beschränkung der Allgemeinheit kann angenommen werden, dass   $M=\{1,\ldots ,n\}$   für   $n\in \mathbb {N}$   ist.

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

$S=2^{M}$

und

$G=\operatorname {Aut} (2^{M})=S_{M}$

und dann noch

$I=\{0,1,\ldots ,n\}$

ist .

Hierbei wird, wie oben dargelegt, die Automorphismengruppe $\operatorname {Aut} (2^{M})$ mit der symmetrischen Gruppe $S_{M}$ identifiziert.

Wie oben erwähnt, hat man als Operation

$S_{M}\times 2^{M}\to 2^{M}$

dabei

$(g,X)\mapsto {g\cdot X}=g(X)\;(g\in S_{M}\;,\;x\subseteq M)$

vorliegen.

Man legt nun für das obige   $A$   eine Antikette der Potenzmenge   $2^{M}$   zugrunde, also ein Mengensystem   ${\mathcal {A}}$   von Teilmengen von $M$, welches so beschaffen ist, dass von diesen Teilmengen keine zwei verschiedene einander umfassen.

Bedeutsam ist nun, dass man stets folgende Kette von Teilmengen innerhalb   $S=2^{M}$   hat:

$C_{0}=\emptyset$

sowie für   $i=1,\ldots ,n$

$C_{i}=\{1,\ldots ,i\}$   .

Damit hat man für   $i=0,\ldots ,n$:

$|S_{M}\cdot C_{i}|=|{M \choose i}|={n \choose i}$

und zudem

$S_{M}\cdot C_{i}\cap {\mathcal {A}}={M \choose i}\cap {\mathcal {A}}=\{X\in {\mathcal {A}}\colon |X|=i\}$   .

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

Denn da   ${\mathcal {A}}$   Antikette ist, kann es niemals vorkommen, dass für zwei unterschiedliche   $i,j$   - etwa   $i<j$   -   $g(C_{i}),g(C_{j})\in {\mathcal {A}}$   gilt, weil nämlich die Inklusion   $C_{i}\subset C_{j}$   stets die Inklusion   $g(C_{i})\subset g(C_{j})$   nach sich zieht (und umgekehrt).

Das heißt jedoch, dass für   $g\in S_{M}$   durchgängig

$|I_{g}|\leq 1$

gilt!

Bezeichnet man nun noch für   $i=0,\ldots ,n$   mit   ${a_{i}}$   die Anzahl der in   ${\mathcal {A}}$   vorkommenden Mengen, welche aus exakt   $i$   Elementen bestehen, so hat man:

$a_{i}=|S_{M}\cdot C_{i}\cap {\mathcal {A}}|$   .

Legt man dann noch die konstante Zahlenfamilie

$w_{0}=w_{1}=\ldots =w_{n}=1$  

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

Weitere Anwendung: Ein allgemeiner Charakterisierungssatz zur LYM-Eigenschaft

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.

Hierbei betrachtet man eine endliche teilweise geordnete Menge

$P\neq \emptyset$

mit der Ordnungsrelation

$\leq$ .

Dabei sei

${\mathcal {O}}=\{O_{1},\dots ,O_{t}\}\subseteq 2^{P}\;(|{\mathcal {O}}|=t\in \mathbb {N} )$

die Menge der verschiedenen Orbits

$\operatorname {Aut} (P)\cdot x=\{g(x):g\in \operatorname {Aut} (P)\}\;(x\in P)$,

welche durch die Operation

$\operatorname {Aut} (P)\times P\to P\;,\;(g,x)\mapsto g\cdot x=g(x)$

der Automorphismengruppe $\operatorname {Aut} (P)$ auf $P$ entstehen.

Weiter sei

${\mathcal {C}}\subseteq 2^{P}$

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

Schließlich sei

${\mathcal {A}}\subseteq 2^{P}$

die Menge der Antiketten innerhalb $P$, also die Menge aller Teilmengen von $P$ mit der Eigenschaft, dass für je zwei darin enthaltene Elemente $x,y$ niemals die Relation $x<y$ erfüllt ist.

Formulierung des allgemeinen Charakterisierungssatzes

Unter den oben genannten Voraussetzungen gilt:

(A) Jeder der Orbits $O_{i}\;(i=1,\dots ,t)$ ist eine Antikette von $P$:

${\mathcal {O}}\subseteq {\mathcal {A}}$ .

(B) Die folgenden vier Bedingungen sind gleichwertig:

(B1)

Für $A\in {\mathcal {A}}$ gilt stets

$\sum _{i=1}^{t}{\frac {|O_{i}\cap A|}{|O_{i}|}}\leq 1$.

(B2)

Jeder der Orbits $O_{i}\;(i=1,\dots ,t)$ ist eine maximale Antikette, wird also von keiner anderen Antikette von $P$ echt umfasst.

(B3)

In $P$ existiert eine Kette, welche zugleich ein Repräsentantensystem der durch die Orbitmenge ${\mathcal {O}}$ gegebenen Partition

$P=O_{1}{\dot {\cup }}O_{2}{\dot {\cup }}\,\dots {\dot {\cup }}O_{t}$

darstellt.

(B4)

Für jede Funktion $w\colon P\rightarrow \mathbb {R}$, bei der sämtliche Restriktionen $w{\upharpoonright }O$ konstante Funktionen sind, gilt

$\max _{A\in {\mathcal {A}}}\;{w[A]}=\max _{i=1,\dots ,t}\;{w[O_{i}]}$.

Beweis des Charakterisierungssatzes

Ad (A)

Die Annahme, es würde für $x\in P$ und $g\in \operatorname {Aut} (P)$

(1) $x<g(x)$

gelten, führt mittels Iteration zu der Ungleichungskette

(2) $x<g(x)<g^{2}(x)<g^{3}(x)<\ldots <g^{n}(x)<g^{n+1}(x)<\ldots \ (\forall n\in \mathbb {N} )$ .

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

Folglich ist jeder $\operatorname {Aut} (P)$-Orbit eine Antikette von $P$ .

Ad (B)

Der Beweis wird in einem Ringschluss geführt. Dazu sei $I=\{1,\dots ,t\}$ .

(B1) → (B2)

Wenn eine Teilmenge $X\subseteq P$ einen Orbit $O_{h}$ echt umfasst, so gilt

(3) $X\supseteq {O_{h}\;{\dot {\cup }}\;\{y\}}$

für mindestens ein $y\in O_{j}$ zu einem Orbit $O_{j}\neq O_{h}$ .

Also folgt

(4) $\sum _{i=1}^{t}{\frac {|O_{i}\cap X|}{|O_{i}|}}\geq {\frac {|O_{h}|}{|O_{h}|}}+{\frac {1}{|O_{j}|}}\geq 1+{\frac {1}{|O_{j}|}}>1$.

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

Schritt 1

Man definiert zunächst eine Hilfsfunktion $\Gamma$, die sich infolge der Tatsache ergibt, dass beliebiges $x\in P$ stets mindestens ein $C\in {\mathcal {C}}$  

- nämlich $C=\{x\}$   -

existiert, so dass

(4) $x\in C\;,\;\max(C)=x$

erfüllt ist.

Also ist vermöge

(5) $\Gamma \colon P\to \mathbb {N} \;;\;x\mapsto \Gamma (x):=\max {\bigl (}\{|C|\colon C\in {\mathcal {C}}\;,\;x\in C\;,\;\max(C)=x\}{\bigr )}\;(x\in P)$

eine sinnvoll erklärte Funktion gegeben.

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

(6) $|\Gamma (P)|\leq \max(\Gamma (P))$.

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

(7) $|\Gamma (P)|\leq \max(\{|C|\colon C\in {\mathcal {C}}\})$ .

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

Deswegen ist vermöge (A) für $C\in {\mathcal {C}}$ stets die Abschätzung

(8) $|O_{i}\cap C|\leq 1\;(i\in I)$

gegeben.

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

(9) $|C|=\sum _{i=1}^{t}{|O_{i}\cap C|}\leq t\;(C\in {\mathcal {C}})$

nach sich.

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

(10) $|\Gamma (P)|\leq \max(\{|C|\colon C\in {\mathcal {C}}\})\leq t$ .

Schritt 2

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

(11) $|\Gamma (P)|=t$

besteht.

Denn:

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

(12) $\max _{C\in {\mathcal {C}}}{|C|}=t$.

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

Das aber heißt:

Es gibt in $P$ eine Kette, welche zugleich ein Repräsentantensystem für die Orbitmenge ${\mathcal {O}}$ darstellt.

Schritt 3

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

Dazu sei

(13) $n_{0}\in \Gamma (P)$ und $P_{n_{0}}=\{x\in P\colon \Gamma (x)=n_{0}\}$ .

$P_{n_{0}}$ ist offenbar eine Antikette von $P$ und zudem nicht die leere Menge.

Man wählt nun irgendein $p\in P_{n_{0}}$ .

Jetzt wird bedeutsam, dass jedes $g\in \operatorname {Aut} (P)$ und ebenso die zugehörige inverse Abbildung $g^{-1}$ die Ordnungsstruktur von $P$ streng erhalten.

Das bedeutet:

Es entsprechen unter $g$ diejenigen Ketten, in denen $p$ das Maximum ist, umkehrbar eindeutig denjenigen Ketten, in denen $g(p)$ das Maximum ist.

Dies zieht die Gleichung

(14) $\Gamma (g(p))=\Gamma (p)=n\;(g\in \operatorname {Aut} (P))$

nach sich.

(14) wiederum bedeutet, dass der Orbit, dem $p$ angehört, etwa $O_{i_{p}}$, ganz in $P_{n_{0}}$ enthalten ist:

(15) $O_{i_{p}}\subseteq P_{n_{0}}$ .

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) $O_{i_{p}}=P_{n_{0}}$ .

Ganz gleichartige Überlegungen lassen sich jedoch für alle $n\in \Gamma (P)$ anstellen. Folglich gilt insgesamt

(17) $\{P_{n}\colon n\in \Gamma (P)\}\subseteq {\mathcal {O}}$ .

Nun ist auch $\{P_{n}\colon n\in \Gamma (P)\}$ eine Partition von $P$ und zwei Partitionen einer Menge können einander niemals echt umfassen.

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

(18) $\{P_{n}\colon n\in \Gamma (P)\}={\mathcal {O}}$ .

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

(19) $|\Gamma (P)|=|\{P_{n}\colon n\in \Gamma (P)\}|=|{\mathcal {O}}|$ .

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

(B3) → (B4)

Es sei $w$ eine reellwertige Funktion, bei der sämtliche Restriktionen $w{\upharpoonright }O$ konstante Funktionen sind. Für ein solches $w$ 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

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

(20) $\max _{A\in {\mathcal {A}}}\;{w[A]}\geq \max _{i\in I}\;{w[O_{i}]}$ .

Schritt 2

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

Dazu sei $A$ eine beliebige Antikette $A\in {\mathcal {A}}$. Hierfür ist die Ungleichung

(21) $w[A]\leq \max _{i\in I}\;{w[O_{i}]}$

zu zeigen.

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

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

(22) $C=\{c_{1},\dots ,c_{t}\}\;{\text{mit}}\;\{c_{i}\}=O_{i}\cap C\;(i\in I)$

enthalten ist.

Es ist damit für $i\in I$ stets

(23) $O_{i}=\operatorname {Aut} (P)\cdot c_{i}$

gültig und daher für jedes $x\in O_{i}$ aufgrund der Beschaffenheit von $w$ in Verbindung mit (22) und (23) durchgängig

(24) $w(x)=w(c_{i})={\frac {w[O_{i}]}{|\operatorname {Aut} (P)\cdot c_{i}|}}$.

Wegen der Partitionseigenschaften von ${\mathcal {O}}$ folgt nun aus (24) sogleich

(25) ${\begin{aligned}w[A]&=\sum _{i\in I}\;{w[O_{i}\cap A]}\\&=\sum _{i\in I}\;{|{\operatorname {Aut} (P)\cdot c_{i}}\cap A|\cdot w(c_{i})}\\&=\sum _{i\in I}\;{{\frac {|{\operatorname {Aut} (P)\cdot c_{i}}\cap A|}{|\operatorname {Aut} (P)\cdot c_{i}|}}\cdot w[O_{i}]}\\\end{aligned}}$ .

An dieser Stelle ist zu berücksichtigen, dass für jeden Automorphismus $g\in \operatorname {Aut} (P)$ mit $C$ auch stets $g(C)$ eine Kette von $P$ ist.

Folglich gilt wegen der Antiketteneigenschaft von $A$ stets

(26) $|g(C)\cap A|\leq 1$ .

Es kann also immer nur höchstens einen einzigen Index $i\in I$ geben mit $g(c_{i})\in A$.

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

(B4) → (B1)

Vermöge

(27) $v\colon P\to \mathbb {R} \;;\;x\mapsto \ v(x):={\frac {1}{|\{g(x):g\in \operatorname {Aut} (P)\}|}}\;(x\in P)$

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

Denn es ist offenbar für $i\in I$ und $x\in O_{i}$ durchgängig

(28) $v(x):={\frac {1}{|O_{i}|}}$ .

Folglich ist für $i\in I$ stets

(29) $v[O_{i}]=|O_{i}|\cdot {\frac {1}{|O_{i}|}}=1$.

Damit aber erhält man unter der Voraussetzung von (B4) für jede Antikette $A\in {\mathcal {A}}$

(30) ${\begin{aligned}\sum _{i=1}^{t}{\frac {|O_{i}\cap A|}{|O_{i}|}}&=\sum _{i\in I}\;{|O_{i}\cap A|\cdot {\frac {1}{|O_{i}|}}}\\&=\sum _{i\in I}\;{v[O_{i}\cap A]}\\&=v[A]\\&\leq \max _{i\in I}\;{v[O_{i}]}\\&=1\\\end{aligned}}$ .

Mit (30) jedoch hat man (B1) .

Nachbetrachtung und Beispiele

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 $P$ in besonders einfacher Art und Weise auf $P$ operiert.

An (B4) - mit $w(x)=1\;(x\in P)$ - wiederum sieht man, dass für ein solches $P$ stets das Analogon zum Satz von Sperner gilt:

Herausragende Beispiele solcher $P$ sind neben den endlichen Potenzmengen vor allem folgende:

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

Quellen und Hintergrundliteratur

• 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.