TY - JOUR

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

AU - Schauz, Uwe

AU - Honold, Thomas

N1 - Funding Information:
We want to thank the reviewers, who made us feel that our work is appreciated by carefully reading all details and pointing out numerous improvements.
Publisher Copyright:
© 2022 Elsevier B.V.

PY - 2023/11

Y1 - 2023/11

N2 - 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.

AB - 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.

KW - Alon and Tarsi's theorem

KW - Balandraud and Girard's theorem

KW - Combinatorial Nullstellensatz

KW - Four color theorem

KW - Jaeger's conjecture

KW - Nowhere zero point

UR - http://www.scopus.com/inward/record.url?scp=85139009601&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2022.113187

DO - 10.1016/j.disc.2022.113187

M3 - Article

AN - SCOPUS:85139009601

SN - 0012-365X

VL - 346

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 11

M1 - 113187

ER -