Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài:A generalization of Combinatorial Nullstellensatz. | A generalization of Combinatorial Nullstellensatz Michal Lason Theoretical Computer Science Department Faculty of Mathematics and Computer Science Jagiellonian University S. Lojasiewicza 6 30-348 Krakow Poland Institute of Mathematics of the Polish Academy of Sciences Sw. Tomasza 30 31-027 Krakow Poland mlason@ Submitted Nov 9 2009 Accepted Oct 5 2010 Published Oct 15 2010 Mathematics Subject Classification 05E99 05A99 05C15 Abstract In this note we give an extended version of Combinatorial Nullstellensatz with weaker assumption on nonvanishing monomial. We also present an application of our result in a situation where the original theorem does not seem to work. 1 Introduction The following theorem of Alon known as Combinatorial Nullstellensatz has numerous applications in Combinatorics Graph Theory and Additive Number Theory see 1 . Theorem 1. Combinatorial Nullstellensatz 1 Let F be an arbitrary field and let f be a polynomial in F x1 . xn . Suppose the coefficient of xai xffi in f is nonzero and deg f I i- Then for any subsets A1 . An of F satisfying Ai a 1 there are ai G A1 . an G An so that f ai . an 0. In this paper we extend this theorem by weakening the assumption on the degree of nonvanishing monomial. We also provide an explicit formula for coefficients of monomials in the usual expansion of f. Similar results were obtained independently by Schauz 5 however our proofs are simple and more direct. The paper is concluded with an application to a graph labeling problem for which classical approach does not seem to work. 2 Generalized Combinatorial Nullstellensatz Let F be an arbitrary field and let f be a polynomial in F x1 . xn . We define the support of f by Supp f a1 . an G Nn the coefficient of xf1 xffi in f is nonzero . On the set Nn and hence also on Supp f we have natural partial order THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 N32 1 ai . an fi 1 . Pn if and only if a fi Pi for all i. The proof of the following theorem is a simple .
