Combinatorial Nullstellensatz

✍ Scribed by Xuding Zhu, R. Balakrishnan

• Publisher: Chapman and Hall/CRC
• Year: 2021
• Tongue: English
• Leaves: 151
• Edition: 1
• Category: Library

✦ Synopsis

Combinatorial Nullstellensatz is a novel theorem in algebra introduced by Noga Alon to tackle combinatorial problems in diverse areas of mathematics. This book focuses on the applications of this theorem to graph colouring. A key step in the applications of Combinatorial Nullstellensatz is to show that the coefficient of a certain monomial in the expansion of a polynomial is nonzero. The major part of the book concentrates on three methods for calculating the coefficients:

• Alon-Tarsi orientation: The task is to show that a graph has an orientation with given maximum out-degree and for which the number of even Eulerian sub-digraphs is different from the number of odd Eulerian sub-digraphs. In particular, this method is used to show that a graph whose edge set decomposes into a Hamilton cycle and vertex-disjoint triangles is 3-choosable, and that every planar graph has a matching whose deletion results in a 4-choosable graph.

• Interpolation formula for the coefficient: This method is in particular used to show that toroidal grids of even order are 3-choosable, r-edge colourable r-regular planar graphs are r-edge choosable, and complete graphs of order p+1, where p is a prime, are p-edge choosable.

• Coefficients as the permanents of matrices: This method is in particular used in the study of the list version of vertex-edge weighting and to show that every graph is (2,3)-choosable.

It is suited as a reference book for a graduate course in mathematics.

✦ Table of Contents

Cover
Half Title
Title Page
Copyright Page
Dedication
Contents
Preface
Authors
Acknowledgements
1. Some Definitions and Notations
2. Combinatorial Nullstellensatz
2.1. Introduction
2.2. An application of CNS to additive number theory
2.3. Application of CNS to geometry
2.4. CNS and a subgraph problem
2.5. 0-1 vectors in a hyperplane
3. Alon–Tarsi Theorem and Its Applications
3.1. Alon-Tarsi theorem
3.2. Bipartite graphs and acyclic orientations
3.3. The Cartesian product of a path and an odd cycle
3.4. A solution to a problem of Erd}os
3.5. Bound for AT(G) in terms of degree
3.6. Planar graphs
3.7. Planar graph minus a matching
3.8. Discharging method
3.9. Hypergraph colouring
3.10. Paintability of graphs
4. Generalizations of CNS and Applications
4.1. Number of non-zero points
4.2. Multisets
4.3. Coefficient of a highest degree monomial
4.4. Calculation of NS(a)
4.5. Alon-Tarsi number of K 2*n and cycle powers
4.6. Alon-Tarsi numbers of toroidal grids
4.7. List colouring of line graphs
4.8. r-regular planar graphs
4.9. Complete graphs K p+1 for odd prime p
4.10. Jaeger's conjecture
5. Permanent and Vertex-edge Weighting
5.1. Permanent as the coefficient
5.2. Edge weighting and total weighting
5.3. Polynomial associated to total weighting
5.4. Permanent index
5.5. Trees with an even number of edges
5.6. Complete graphs
5.7. Every graph is (2,3)-choosable
Bibliography
Index