Andrii Arman

(Department of Mathematics, University of Manitoba)

Combinatorial Nullstellensatz

Date Friday, January 17, 2014

Based on a theorem by Hilbert, the Combinatorial Nullstellensatz (CN) is a theorem, discovered by Alon, Nathanson and Ruzsa in 1989 and further developed in the 90s. This theorem appears to be a powerful tool used in Additive Number Theory, Graph Theory and Combinatorics. CN was used to give short proofs of the Cauchy--Davenport Theorem, and other results considering restricted sums. It was also used to answer some graph theory questions regarding regular subgraphs, and vertex colorings.
In this talk I will show different applications of CN, including the Alon-Tarsi Theorem that shows a graph is k-colourable if and only if some polynomial associated with the graph satisfies some algebraic property.