Pure Mathematics Seminar: The Combinatorial Nullstellensatz, Alon and Tarsi's Conjecture and the Four Color Problem

Events

Title

The Combinatorial Nullstellensatz, Alon and Tarsi's Conjecture and the Four Color Problem

Abstract

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.

Speaker

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.