(Department of Mathematics, University of Manitoba)
|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.