Combinatorial Nullstellensatz: With Applications to Graph Colouring
Der kombinatorische Nullstellensatz ist ein neues Theorem in der Algebra, das von Noga Alon eingeführt wurde, um kombinatorische Probleme in verschiedenen Bereichen der Mathematik zu lösen. Dieses Buch konzentriert sich auf die Anwendungen dieses Theorems auf die Färbung von Graphen. Ein wichtiger Schritt bei der Anwendung des kombinatorischen Nullstellensatzes besteht darin, zu zeigen, dass der Koeffizient eines bestimmten Monoms in der Entwicklung eines Polynoms ungleich Null ist. Der Hauptteil des Buches konzentriert sich auf drei Methoden zur Berechnung der Koeffizienten:
⬤ Alon-Tarsi-Orientierung: Die Aufgabe besteht darin, zu zeigen, dass ein Graph eine Orientierung mit gegebenem maximalem Außengrad hat, für die die Anzahl der geraden Eulerschen Teildigraphen von der Anzahl der ungeraden Eulerschen Teildigraphen verschieden ist. Insbesondere wird diese Methode verwendet, um zu zeigen, dass ein Graph, dessen Kantenmenge sich in einen Hamilton-Zyklus und vertex-disjoint Dreiecke zerlegt, 3-choosable ist, und dass jeder planare Graph ein Matching hat, dessen Streichung zu einem 4-choosable Graph führt.
⬤ Interpolationsformel für den Koeffizienten: Diese Methode wird insbesondere verwendet, um zu zeigen, dass toroidale Gitter gerader Ordnung 3-wählbar sind, r-Kanten-farbige r-reguläre planare Graphen r-Kanten-wählbar sind und vollständige Graphen der Ordnung p+1, wobei p eine Primzahl ist, p-Kanten-wählbar sind.
⬤ Koeffizienten als Permanenzen von Matrizen: Diese Methode wird insbesondere bei der Untersuchung der Listenversion der Scheitelpunkt-Kanten-Gewichtung verwendet und um zu zeigen, dass jeder Graph (2,3)-wählbar ist.
Das Buch eignet sich als Nachschlagewerk für einen Graduiertenkurs in Mathematik.
| ISBN: | 9780367686949 |
| Autor: | |
| Verlag: | |
| Einband: | Hardcover |
| Erscheinungsjahr: | 2021 |
| Seitenzahl: | 134 |
Derzeit verfügbar, auf Lager.
