2010/08/17 by Géza Kós, Kós, Géza, Lajos Rónyai +1 · 1 citation
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #Rings, Modules, and Algebras #graph theory and CDMA systems #math.AC #math.CO #msc:05E40
paper · pdf · doi:10.48550/arxiv.1008.2901
Submitted to the journal Combinatorica of the János Bolyai Mathematical Society on August 5, 2010
arxiv created 2011/09/23 · arxiv updated 2011/09/26
Alon's combinatorial Nullstellensatz (Theorem 1.1 from \citeAlon1) is one of the most powerful algebraic tools in combinatorics, with a diverse array of applications. Let \F be a field, S1,S2,..., Sn be finite nonempty subsets of \F. Alon's theorem is a specialized, precise version of the Hilbertsche Nullstellensatz for the ideal of all polynomial functions vanishing on the set S=S1× S2× ... × Sn⊆ \Fn. From this Alon deduces a simple and amazingly widely applicable nonvanishing criterion (Theorem 1.2 in \citeAlon1). It provides a sufficient condition for a polynomial f(x1,...,xn) which guarantees that f is not identically zero on the set S. In this paper we extend these two results from sets of points to multisets. We give two different proofs of the generalized nonvanishing theorem. We extend some of the known applications of the original nonvanishing theorem to a setting allowing multiplicities, including the theorem of Alon and Füredi on the hyperplane coverings of discrete cubes.