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

Bearbeiten

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

Gegeben seien zwei natürliche Zahlen   und dazu eine endliche Grundmenge   mit   Elementen.
Weiter gegeben seien zwei Zerlegungen   und   von   in Klassen gleicher Größe; also dergestalt, dass stets die Gleichungen   erfüllt sind.
Dann gilt:
Unter diesen Gegebenheiten besitzen   und   immer ein gemeinsames Vertretersystem; also ein Vertretersystem derart, dass jede  -Klasse und jede  -Klasse von genau einem dieser Vertreter repräsentiert wird .

Folgerung: Der Satz von Miller

Bearbeiten

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

Bearbeiten

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  -Faktor.[5]

Ü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  -reguläre bipartite Graph ( ) zerfällt in      -Faktoren.[7]

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   Kanten zusammen, so kann man die Kantenmenge so in   Klassen zerlegen, dass je zwei benachbarte Kanten stets verschiedenen Klassen angehören.

Mit anderen Worten:

Ist der Maximalgrad eines endlichen bipartiten Graphen gleich  , so ist er  -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:
   .

Siehe auch

Bearbeiten

Literatur

Bearbeiten

Originalarbeiten

Monographien

Einzelnachweise und Anmerkungen

Bearbeiten
  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 „ -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   Faktoren zugrundeliegende Knotenmenge ist dabei dieselbe, während die Faktorisierung eine Zerlegung der Kantenmenge in   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