The Combinatorial Nullstellensatz, Alon and Tarsi's Conjecture and the Four Color Problem
We start by introducing and explaining the Quantitative Combinatorial Nullstellensatz, a strengthened version of Alon’s Combinatorial Nullstellensatz. This theorem has very many applications. It is often used to prove that combinatorial problems with a trivial solution (but bounded “complexity”) also must have a non-trivial solution. We will briefly explain that, but then turn towards a problem with no trivial solutions – Alon and Tarsi’s conjecture that every non-singular n × n matrix A , over a finite field F_q with q > 3 elements, has a nowhere zero point. Here, a nowhere zero point of A is a vector x in F_q^n such that neither x nor Ax has a zero entry. Alon and Tarsi could prove their conjecture for all non-prime cardinalities q . We give a new short proof of their partial result. Afterwards, we discuss a connection between nowhere zero points and the four color problem.
Professor Uwe Schauz
Dr Uwe Schauz joined XJTLU as a lecture in 2012 and now is an associated professor in the department of Mathematics at XJTLU.