Satz von van der Waerden (Zerlegung endlicher Mengen)

Der Satz von van der Waerden über die Zerlegung endlicher Mengen ist ein mathematischer Lehrsatz, welcher sowohl der Mengenlehre als auch der Graphentheorie zugerechnet werden kann. Er geht zurück auf den niederländischen Mathematiker Bartel Leendert van der Waerden, der ihn im Jahre 1927 publizierte. Der Satz behandelt Zerlegungen endlicher Mengen und ist engstens verwandt mit einem graphentheoretischen Satz des ungarischen Mathematikers Dénes Kőnig über reguläre bipartite Graphen aus dem Jahr 1914.

Formulierung des Satzes

Der Satz lässt sich angeben wie folgt:^[1][2]

Gegeben seien zwei natürliche Zahlen ${\displaystyle n,k\in \mathbb {N} }$ und dazu eine endliche Grundmenge ${\displaystyle X}$ mit ${\displaystyle n\cdot k}$ Elementen.

Weiter gegeben seien zwei Zerlegungen ${\displaystyle {\mathcal {A}}=(A_{1},\ldots ,A_{n})}$ und ${\displaystyle {\mathcal {B}}=(B_{1},\ldots ,B_{n})}$ von ${\displaystyle X}$ in Klassen gleicher Größe; also dergestalt, dass stets die Gleichungen ${\displaystyle |A_{i}|=k=|B_{j}|\;(i,j=1,\ldots ,n)}$ erfüllt sind.

Dann gilt:

Unter diesen Gegebenheiten besitzen ${\displaystyle {\mathcal {A}}}$ und ${\displaystyle {\mathcal {B}}}$ immer ein gemeinsames Vertretersystem; also ein Vertretersystem derart, dass jede ${\displaystyle {\mathcal {A}}}$-Klasse und jede ${\displaystyle {\mathcal {B}}}$-Klasse von genau einem dieser Vertreter repräsentiert wird .

Folgerung: Der Satz von Miller

B. L. van der Waerden hat seinen Satz als direkte Verallgemeinerung eines gruppentheoretischen Satzes des US-amerikanischen Mathematikers George Abram Miller gefunden und formuliert. Der millersche Satz ergibt sich, wenn man den van der Waerden’schen Satz auf die Rechts- und Linksnebenklassen der Untergruppen endlicher Gruppen anwendet. Zusammenhängend formuliert besagt der Satz von Miller also:^[1][2]

In einer endlichen Gruppe gibt es für die Rechts- und Linksnebenklassen einer jeden Untergruppe stets ein gemeinsames Vertretersystem.

Zusammenhang mit bipartiten Graphen: Ein Satz von Kőnig in drei Versionen

I

Wie Dénes Kőnig in seiner Monographie Theorie der endlichen und unendlichen Graphen darlegt und auch B. L. van der Waerden in seiner 1927er Arbeit anmerkt, ist der van der Waerden’sche Satz gleichwertig mit einem frühen graphentheoretischen Satz von Dénes Kőnig, der sich (in moderner Formulierung) folgendermaßen angeben lässt:^[3][4]

Ein endlicher regulärer bipartiter Graph besitzt stets einen ${\displaystyle 1}$-Faktor.^[5]

II

Über den obigen Satz hat Kőnig zum ersten Mal in 1914 auf dem Pariser Kongress für mathematische Philosophie vorgetragen und dabei zugleich auf die Gleichwertigkeit mit dem folgenden Satz hingewiesen:^[6]

Jeder endliche ${\displaystyle m}$-reguläre bipartite Graph (${\displaystyle m\in \mathbb {N} }$) zerfällt in ${\displaystyle m}$   ${\displaystyle 1}$-Faktoren.^[7]

III

Wie Kőnig weiter zeigt, sind die beiden zuletzt zitierten Sätze ihrerseits gleichwertig mit einem von ihm im Jahre 1916 publizierten Satz, der sich formulieren lässt wie folgt:^[6][8]

Laufen in jedem Knoten eines endlichen bipartiten Graphen höchstens ${\displaystyle m}$ Kanten zusammen, so kann man die Kantenmenge so in ${\displaystyle m}$ Klassen zerlegen, dass je zwei benachbarte Kanten stets verschiedenen Klassen angehören.

Mit anderen Worten:

Ist der Maximalgrad eines endlichen bipartiten Graphen gleich ${\displaystyle m}$, so ist er ${\displaystyle m}$-kantenfärbbar.

Dies bedeutet jedoch nichts weiter als das folgende Resultat:^[9]

Für einen endlichen bipartiten Graphen sind Kantenfärbungszahl und Maximalgrad stets identisch, also:

${\displaystyle \chi ^{\prime }(G)=\Delta (G)}$  .

Siehe auch

• Satz von Vizing

Literatur

Originalarbeiten

• G. A. Miller: On a method due to Galois. In: Quarterly Journal of Mathematics. Band 41, 1910, S. 382–384. 
• Dénes König: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. In: Mathematische Annalen. Band 77, 1916, S. 453–465 (link.springer.com).  MR1511872
• Bartel L. van der Waerden: Ein Satz über Klasseneinteilungen von endlichen Mengen. In: Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. Band 5, 1927, S. 185–188 (link.springer.com).  MR3069474

Monographien

• Rudolf Halin: Graphentheorie I (= Erträge der Forschung. Band 138). Wissenschaftliche Buchgesellschaft, Darmstadt 1980, ISBN 3-534-06767-3 (MR0586234). 
• Dénes König: Theorie der endlichen und unendlichen Graphen. Mit einer Abhandlung von L. Euler. Hrsg.: H. Sachs (= Teubner-Archiv zur Mathematik. Band 6). BSB B. G. Teubner Verlagsgesellschaft, Leipzig 1986, ISBN 3-211-95830-4 (MR0886676). 
• Reinhard Diestel: Graph Theory (= Graduate Texts in Mathematics. Band 173). 3. Auflage. Springer Verlag, Berlin / Heidelberg / New York 2005, ISBN 3-540-26182-6 (MR2159259). 

Einzelnachweise und Anmerkungen

1. ↑ ^{a b} Bartel L. van der Waerden: Ein Satz … . In: Abh. Math. Sem. Univ. Hamburg, 5, S. 185–188
2. ↑ ^{a b} Dénes König: Theorie der endlichen und unendlichen Graphen. 1986, S. 171 ff., 176–177
3. ↑ Bartel L. van der Waerden: Ein Satz über Klasseneinteilungen von endlichen Mengen. In: Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. Band 5, 1927, S. 187 (link.springer.com). 
4. ↑ Dénes König: Theorie der endlichen und unendlichen Graphen. 1986, S. 171, 176.
5. ↑ Wie Rudolf Halin in seiner Graphentheorie I anmerkt (S. 166), fallen für bipartite Graphen die Begriffe „${\displaystyle 1}$-Faktor“ und „vollständige Paarung“ zusammen.
6. ↑ ^{a b} Dénes König: Theorie der endlichen und unendlichen Graphen. 1986, S. 170–171.
7. ↑ Die dem Graphen und seinen ${\displaystyle m}$ Faktoren zugrundeliegende Knotenmenge ist dabei dieselbe, während die Faktorisierung eine Zerlegung der Kantenmenge in ${\displaystyle m}$ Teilmengen bewirkt.
8. ↑ Dénes König: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. In: Mathematische Annalen, Band 77, 1916, S. 453–456
9. ↑ Reinhard Diestel: Graph Theory. 2005, S. 119