Combinatorial Nullstellensatz: Various Proofs, Extensions and Applications
Yulia Alexandr · 2019
The Combinatorial Nullstellensatz is an algebraic technique first introduced by Noga Alon in 1999. Being closely related to the famous Hilbert's Nullstellensatz, it has extensive applications in combinatorics and number theory where various results are obtained by analyzing roots of well-chosen polynomials. In this thesis, we present the two main theorems associated with the Combinatorial Nullstellensatz along with their original proofs. Moreover, we give attention to alternative proofs and extensions of these theorems that were introduced in later papers by other researchers as well as discuss several existing applications, focusing our attention on those in graph theory. Using the Combinatorial Nullstellensatz, we give a necessary and sufficient condition for an m-uniform hypergraph to be k-colorable, thus generalizing one of Alon's results. We also introduce a fun application of the Combinatorial Nullstellensatz in determining the existence of solutions to the well-known Sudoku Puzzle.