Combinatorial Nullstellensatz (Q4243069)

In this interesting paper some consequences of the fundamental theorem called ``Hilbert's Nullstellensatz'', that asserts that if \(F\) is an algebraically closed field, and \(f,g_{1},\dots ,g_{m}\) are polynomials in the ring of polynomials \(F[x_{1},\dots ,x_{n}]\), where \(f\) vanishes over all common zeros of \(g_{1},\dots ,g_{m}\), then there is an integer \(k\) and polynomials \(h_{1},\dots ,h_{m}\) in \(F[x_{1},\dots ,x_{n}]\) so that \(f^{k}=\sum_{i=1}^{n}h_{i}g_{i}\), are applied in combinatorial number theory, in graph theory and in combinatorics. After presenting in Section 2 the proofs of two theorems occurring in the special case when \(m=n\) and each \(g_{i}\) is a univariate polynomial of the form \(\prod_{s\in S_{i}}(x_{i}-s)\), where \(S_{1},\dots ,S_{n}\) are nonempty subsets of \(F\), in Section 3 it is shown that the classical theorem of Chevalley and Warning on roots of systems of polynomials and the basic theorem of Cauchy and Davenport on the addition of residue classes follow as simple consequences. In Sections 4, 5, 6, 7 and 8 additional applications in additive number theory (extensions of the Cauchy-Davenport theorem; set addition in vector spaces over prime fields) and in graph theory and combinatorics (graphs, subgraphs and cubes; graph colouring; the permanent lemma) are described. Many of these applications are known results, proved here in a unified way, and some are new. There are several known results that assert that a combinatorial structure satisfies a certain combinatorial property if and only if an appropriate polynomial associated with it lies in a properly defined ideal. In Section 9 this technique based upon ideals of polynomials is applied and several results of this form are deduced (on graphs that do not contain an independent set of a given cardinality, or are not \(k\)-colourable, or have the bandwidth bounded below by a given number). Finally, Section 10 contains some concluding remarks and open problems.