Über ein Theorem von Hans Läuchli

Für natürliche Zahlen n sei P_n die folgende Aussage: Ist G ein unendlicher Graph, all dessen endliche Teilgraphen n-färbbar sind, so ist auch G selber n-färbbar. 1961 hat Mycielski gezeigt, dass P_n (für beliebige n) aus dem Primidealtheorem folgt. Umgekehrt gelang es Läuchli 1971 zu zeigen, dass das Primidealtheorem aus P₃ folgt, womit also für alle natürlichen Zahlen m,n grösser als 2 gilt ''P_m impliziert P_n''. Der Beweis, den Läuchli gegeben hat, ist relativ kompliziert, und am Schluss seines Beweises stellt er die Aufgabe, einen direkten Beweis für ''P₃ impliziert P₄'' zu finden (also ohne das Primidealtheorem zu benutzen). Das Ziel dieses Artikels ist es nun, einen solchen Beweis zu führen.

back to publications