Transformation invariance in the Combinatorial Nullstellensatz and nowhere-zero points of non-singular matrices

Uwe Schauz*, Thomas Honold

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


We describe a kind of transformation invariance in the Quantitative Combinatorial Nullstellensatz. This transformation invariance is frequently used to prove list coloring theorems. We describe its usage in a new short proof of Balandraud and Girard's Theorem about zero-sum subsums. We also use the transformation invariance to study nowhere-zero points of non-singular matrices A∈Fn×n, which are points x∈Fn such that neither x nor Ax have zero entries. Utilizing the non-singularity of A in an elegant way, we give a new proof of Alon and Tarsi's Theorem about the existence of nowhere-zero points over fields F that are not prime. Afterwards, with other methods, we extend the scope of Alon, Tarsi and Jaeger's Conjecture from fields to rings. Partially proving this extension, we show that over rings that are not fields, every invertible matrix has a nowhere-zero point. Moreover, over the integers modulo m, non-vanishing determinant suffices to guarantee nowhere-zero points, as we prove for all m that are not a prime power. Finally, we show that the four color problem can be stated as an existence problem for nowhere-zero points over the field with three elements.

Original languageEnglish
Article number113187
JournalDiscrete Mathematics
Issue number11
Publication statusPublished - Nov 2023


  • Alon and Tarsi's theorem
  • Balandraud and Girard's theorem
  • Combinatorial Nullstellensatz
  • Four color theorem
  • Jaeger's conjecture
  • Nowhere zero point


Dive into the research topics of 'Transformation invariance in the Combinatorial Nullstellensatz and nowhere-zero points of non-singular matrices'. Together they form a unique fingerprint.

Cite this