Nullstellensatz combinatorio: con applicazioni alla colorazione dei grafici

Titolo originale:

Combinatorial Nullstellensatz: With Applications to Graph Colouring

Contenuto del libro:

Il Nullstellensatz combinatorio è un nuovo teorema dell'algebra introdotto da Noga Alon per affrontare problemi combinatori in diverse aree della matematica. Questo libro si concentra sulle applicazioni di questo teorema alla colorazione dei grafi. Un passo fondamentale nelle applicazioni del Combinatorial Nullstellensatz è dimostrare che il coefficiente di un certo monomio nell'espansione di un polinomio è non nullo. La parte principale del libro si concentra su tre metodi per il calcolo dei coefficienti:

⬤ Orientamento di Alon-Tarsi: Il compito è dimostrare che un grafo ha un'orientazione con un dato grado massimo e per la quale il numero di sottodigrafi euleriani pari è diverso dal numero di sottodigrafi euleriani dispari. In particolare, questo metodo viene utilizzato per dimostrare che un grafo il cui insieme di bordi si decompone in un ciclo di Hamilton e in triangoli con vertici disgiunti è 3-scelto, e che ogni grafo planare ha una corrispondenza la cui eliminazione risulta in un grafo 4-scelto.

⬤ Formula di interpolazione per il coefficiente: Questo metodo viene utilizzato in particolare per dimostrare che i reticoli toroidali di ordine pari sono 3-scelti, che i grafi planari r-edge colourable r-regular sono r-edge choosable e che i grafi completi di ordine p+1, dove p è un primo, sono p-edge choosable.

⬤ Coefficienti come permanenti di matrici: Questo metodo viene utilizzato in particolare nello studio della versione a liste della ponderazione vertice-bordo e per dimostrare che ogni grafo è (2,3)-scegliibile.

È adatto come libro di riferimento per un corso di laurea in matematica.