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   $\mathrm{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

$\mathrm{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

$(\genfrac{}{}{0ex}{}{M}{i})\subseteq 2^M(i=0,\dots ,|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   $\mathrm{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\le \underset{g\in G}{\max }\sum _{i\in I_g}{w}_i$.

Beweis

Schritt 1

Wir setzen

$G^i=\{g\in G:g\cdot c_i\in A\}$   $(\mathrm{\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:G\times I\to ℝ,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\}]\le |G|\underset{g\in G}{\max }v[\{g\}\times I_g]$   .

Aus (3) gelangt man sogleich zu der Ungleichung

(4) $\sum _{i\in I}|G^i|\cdot w_i\le |G|\underset{g\in G}{\max }\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:g\cdot c=a\}|=\sum _{a\in (G\cdot c\cap A)}|\{g\in G: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) $h{G}_c=\{g\in G: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^{\text{'}}\in G_c$.

Es gilt dann

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

und folglich

(11) $h{G}_c\subseteq \{g\in G: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:g\cdot c=a\}\subseteq h{G}_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\le \underset{i\in I}{\max }{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,\dots ,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=\mathrm{Aut}(2^M)=S_M$

und dann noch

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

ist .

Hierbei wird, wie oben dargelegt, die Automorphismengruppe $\mathrm{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   $𝒜$   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=\mathrm{\varnothing }$

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

$C_i=\{1,\dots ,i\}$   .

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

$|S_M\cdot C_i|=|(\genfrac{}{}{0ex}{}{M}{i})|=(\genfrac{}{}{0ex}{}{n}{i})$

und zudem

$S_M\cdot C_i\cap 𝒜=(\genfrac{}{}{0ex}{}{M}{i})\cap 𝒜=\{X\in 𝒜:|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   $𝒜$   Antikette ist, kann es niemals vorkommen, dass für zwei unterschiedliche   $i,j$   - etwa   $i<j$   -   $g(C_i),g(C_j)\in 𝒜$   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|\le 1$

gilt!

Bezeichnet man nun noch für   $i=0,\dots ,n$   mit   $a_i$   die Anzahl der in   $𝒜$   vorkommenden Mengen, welche aus exakt   $i$   Elementen bestehen, so hat man:

$a_i=|S_M\cdot C_i\cap 𝒜|$   .

Legt man dann noch die konstante Zahlenfamilie

$w_0=w_1=\dots =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\ne \mathrm{\varnothing }$

mit der Ordnungsrelation

$\le$ .

Dabei sei

$𝒪=\{O_1,\dots ,O_t\}\subseteq 2^P(|𝒪|=t\in \mathbb{N})$

die Menge der verschiedenen Orbits

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

welche durch die Operation

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

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

Weiter sei

$𝒞\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\le y$ oder die Relation $y\le x$ erfüllt ist.

Schließlich sei

$𝒜\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$:

$𝒪\subseteq 𝒜$ .

(B) Die folgenden vier Bedingungen sind gleichwertig:

(B1)

Für $A\in 𝒜$ gilt stets

$\sum _{i=1}^t\frac{|O_i\cap A|}{|O_i|}\le 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 $𝒪$ gegebenen Partition

$P=O_1\dot{\cup }{O}_2\dot{\cup }\dots \dot{\cup }{O}_t$

darstellt.

(B4)

Für jede Funktion $w:P\to ℝ$, bei der sämtliche Restriktionen $w\upharpoonright O$ konstante Funktionen sind, gilt

$\underset{A\in 𝒜}{\max }w[A]=\underset{i=1,\dots ,t}{\max }w[O_i]$.

Beweis des Charakterisierungssatzes

Ad (A)

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

(1) $x<g(x)$

gelten, führt mittels Iteration zu der Ungleichungskette

(2) $x<g(x)<g^2(x)<g^3(x)<\dots <g^n(x)<g^{n+1}(x)<\dots (\mathrm{\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 $\mathrm{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\ne O_h$ .

Also folgt

(4) $\sum _{i=1}^t\frac{|O_i\cap X|}{|O_i|}\ge \frac{|O_h|}{|O_h|}+\frac{1}{|O_j|}\ge 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 $\mathrm{\Gamma }$, die sich infolge der Tatsache ergibt, dass beliebiges $x\in P$ stets mindestens ein $C\in 𝒞$  

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

existiert, so dass

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

erfüllt ist.

Also ist vermöge

(5) $\mathrm{\Gamma }:P\to \mathbb{N};x\mapsto \mathrm{\Gamma }(x):=\max (\{|C|:C\in 𝒞,x\in C,\max (C)=x\})(x\in P)$

eine sinnvoll erklärte Funktion gegeben.

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

(6) $|\mathrm{\Gamma }(P)|\le \max (\mathrm{\Gamma }(P))$.

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

(7) $|\mathrm{\Gamma }(P)|\le \max (\{|C|:C\in 𝒞\})$ .

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 𝒞$ stets die Abschätzung

(8) $|O_i\cap C|\le 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|\le t(C\in 𝒞)$

nach sich.

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

(10) $|\mathrm{\Gamma }(P)|\le \max (\{|C|:C\in 𝒞\})\le t$ .

Schritt 2

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

(11) $|\mathrm{\Gamma }(P)|=t$

besteht.

Denn:

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

(12) $\underset{C\in 𝒞}{\max }|C|=t$.

D mit $P$ auch $𝒞$endlich ist , zieht (12) in Verbindung nach sich, dass für mindestens ein $C\in 𝒞$ 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 $𝒪$ darstellt.

Schritt 3

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

Dazu sei

(13) $n_0\in \mathrm{\Gamma }(P)$ und $P_{n_0}=\{x\in P:\mathrm{\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 \mathrm{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) $\mathrm{\Gamma }(g(p))=\mathrm{\Gamma }(p)=n(g\in \mathrm{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 \mathrm{\Gamma }(P)$ anstellen. Folglich gilt insgesamt

(17) $\{P_n:n\in \mathrm{\Gamma }(P)\}\subseteq 𝒪$ .

Nun ist auch $\{P_n:n\in \mathrm{\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:n\in \mathrm{\Gamma }(P)\}=𝒪$ .

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

(19) $|\mathrm{\Gamma }(P)|=|\{P_n:n\in \mathrm{\Gamma }(P)\}|=|𝒪|$ .

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) $\underset{A\in 𝒜}{\max }w[A]\ge \underset{i\in I}{\max }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 𝒜$. Hierfür ist die Ungleichung

(21) $w[A]\le \underset{i\in I}{\max }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=\mathrm{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]}{|\mathrm{Aut}(P)\cdot c_i|}$.

Wegen der Partitionseigenschaften von $𝒪$ folgt nun aus (24) sogleich

(25) $\begin{array}{cc}w[A]& =\sum _{i\in I}w[O_i\cap A]\\ & =\sum _{i\in I}|\mathrm{Aut}(P)\cdot c_i\cap A|\cdot w(c_i)\\ & =\sum _{i\in I}\frac{|\mathrm{Aut}(P)\cdot c_i\cap A|}{|\mathrm{Aut}(P)\cdot c_i|}\cdot w[O_i]\\ \end{array}$ .

An dieser Stelle ist zu berücksichtigen, dass für jeden Automorphismus $g\in \mathrm{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|\le 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:P\to ℝ;x\mapsto v(x):=\frac{1}{|\{g(x):g\in \mathrm{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 𝒜$

(30) $\begin{array}{cc}\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]\\ & \le \underset{i\in I}{\max }v[O_i]\\ & =1\\ \end{array}$ .

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

• Vorlage:Literatur MR0892525
• Vorlage:Literatur MR1429390
• D. Lubell: A short proof of Sperner's lemma. Journal of Combinatorial Theory, Vol. 1, 2 (1966): 299. Vorlage:DOI, 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. Vorlage:DOI, MR0150049
• Vorlage:Literatur [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.