Alon%26apos;s Nullstellensatz for multisets

作者：Kos Geza^*; Ronyai Lajos

来源：Combinatorica, 2012, 32(5): 589-605.

DOI：10.1007/s00493-012-2758-0

Alon%26apos;s combinatorial Nullstellensatz (Theorem 1.1 from [2]) is one of the most powerful algebraic tools in combinatorics, with a diverse array of applications. Let be a field, S (1), S (2),..., S (n) be finite nonempty subsets of . Alon%26apos;s theorem is a specialized, precise version of the Hilbertsche Nullstellensatz for the ideal of all polynomial functions vanishing on the set . From this Alon deduces a simple and amazingly widely applicable nonvanishing criterion (Theorem 1.2 in [2]). It provides a sufficient condition for a polynomial f(x (1),..., x (n)) 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 Furedi on the hyperplane coverings of discrete cubes.

• 出版日期2012-5