Graph polynomials and group coloring of graphs

European Journal of Combinatorics 102 (2022) 103505 Contents lists available at ScienceDirect European Journal of Combinatorics journal homepage: www.elsevier.com/locate/ejc Graph polynomials and group coloring of graphs✩ Bartłomiej Boseka, Jarosław Grytczukb, Grzegorz Gutowskia, Oriol Serrac, Mariusz Zającb aInstitute of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland bFaculty of Mathematics and Information Science, Warsaw University of Technology, Warsaw, Poland cDepartment of Mathematics, Universitat Politècnica de Catalunya, Barcelona, Spain article info Article history: Received 13 February 2021 Accepted 15 December 2021 Available online 12 January 2022 abstract Let Γbe an Abelian group and let Gbe a simple graph. We say that Gis Γ-colorable if for some fixed orientation of Gand every edge labeling ℓ:E(G)→Γ, there exists a vertex coloring cby the elements of Γsuch that c(y)−c(x)= ℓ(e), for every edge e=xy (oriented from xto y). Langhede and Thomassen proved recently that every planar graph on nvertices has at least 2n/9different Z5-colorings. By using a different approach based on graph polynomials, we extend this result to K5-minor-free graphs in the more general setting of field coloring. More specifically, we prove that every such graph on nvertices is F-5-choosable, whenever Fis an arbitrary field with at least 5 elements. Moreover, the number of colorings (for every list assignment) is at least 5n/4. ©2022TheAuthors.PublishedbyElsevierLtd.Thisisanopen accessarticleundertheCCBY-NC-NDlicense (http://creativecommons.org/licenses/by-nc-nd/4.0/). 1. Introduction Let Γbe an Abelian group and let Gbe a simple graph. We say that Gis Γ-colorable if for some orientation of Gand every edge labeling ℓby the elements of Γthere exists a vertex coloring cby ✩Supported by the Polish National Science Center, Grant Number: NCN 2019/35/B/ST6/02472. Oriol Serra acknowledges financial support from the Spanish Agencia Estatal de Investigación under project MTM2017-82166-P. E-mail addresses: [email protected] (B. Bosek), [email protected] (J. Grytczuk), [email protected] (G. Gutowski), [email protected] (O. Serra), [email protected] (M. Zając). https://doi.org/10.1016/j.ejc.2021.103505 0195-6698/©2022 The Authors. Published by Elsevier Ltd. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). B. Bosek, J. Grytczuk, G. Gutowski et al. European Journal of Combinatorics 102 (2022) 103505 the elements of Γsuch that c(y)−c(x)= ℓ(e), for every edge e=xy (oriented from xtowards y). This notion was introduced by Jaeger, Linial, Payane and Tarsi [9] as a dual concept to group connectivity. Answering a question posed in [9], Lai and Zhang [11] proved that every planar graph is Z5colorable. Recently, Langhede and Thomassen [12] strengthened this result by proving that the number of Z5-colorings of every planar graph on nvertices (for any fixed edge labeling) is at least 2n/9. The proof is elementary but quite involved. In this paper we further extend these results by using the polynomial method. It is convenient to introduce a slightly more general setting. Let Fbe an arbitrary field and let Gbe a simple graph. Suppose that each edge e=xy of Gis assigned a triple (ae,be,ce)∈F3, with ae,be= 0. We say that Gis F-colorable if for every such edge labeling there exists a vertex coloring fby the elements of F such that aef(x)+bef(y)+ce= 0, for every edge e=xy. Clearly, F-colorability of a graph implies its Γ-colorability, where Γis the additive group of the field F. Define a graph Gto be F-k-choosable if it is F-colorable from arbitrary lists of elements of F, each of size k, assigned to the vertices. Theorem 1. Let G be a graph on n vertices without a minor of K5. Let Fbe an arbitrary field with at least 5elements. Then G is F-5-choosable. Moreover, the number of colorings (for any fixed list assignment and any fixed edge labeling) is at least 5n/4. The proof is based on the method of graph polynomials. We use two tools, the Combinatorial Nullstellensatz of Alon [2] and a result of Alon and Füredi [3] concerning the number of non-zero values of a polynomial evaluated at all points of a multidimensional grid. Notice that Theorem 1 only covers Abelian groups that are additive groups of a field. For a general Abelian group Γof order at least 5, Chuang, Lai, Omidi, Wang, and Zakeri proved in [6] by elementary methods that every K5-minor free graph is Γ-5-choosable. Theorem 1 does not extend this result, but in the overlapping cases guarantees a stronger conclusion, and also easily implies it in the case of arbitrary cyclic groups Γ(Theorem 10). 2. The results 2.1. Graph polynomials Let Gbe a simple graph on the set of vertices V(G)= {x1,x2,...,xn}. Let PGbe the graph polynomial of G, defined by PG(x1,x2,...,xn)=∏ xixj∈E(G),i<j (xi−xj).(2.1) We identify symbols denoting vertices of Gwith variables of PG. We may consider PGas a polynomial over an arbitrary field F. In the process of expanding the polynomial PG, one creates monomials by picking one variable from each factor (xi−xj). Thus, every monomial corresponds to the unique orientation of Gobtained by directing the edge xixjtowards the picked variable. Thus, the degrees of the variables in the monomial coincide with the in-degrees of the vertices in the corresponding orientation. Let MGdenote the multi-set of all monomials arising in this way. So, the cardinality of MGis equal to 2m, where m= |E(G)|, and the multiplicity of each monomial Mis equal to the number of orientations of Gsharing the same in-degree sequence (corresponding to the degrees of the variables in M). The sign of a monomial M∈MGis the product of signs of all variables picked to form M. The coefficient of a monomial Min PG, denoted as cM(PG), is the sum of signs of all copies of Min MG. A monomial Mis called non-vanishing in PGif cM(PG)= 0. Suppose now that each edge e=xixjof a graph G(oriented so that i<j) is assigned an arbitrary pair (ae,be) of non-zero elements of F. We say that the edges of Gare decorated with pairs (a,b), and we define the corresponding decorated graph polynomial DGin which every factor (xi−xj) corresponding to the edge e=xixjdecorated with (ae,be) is substituted with (aexi+bexj): DG(x1,x2,...,xn)=∏ e=xixj∈E(G),i<j (aexi+bexj).(2.2) 2 B. Bosek, J. Grytczuk, G. Gutowski et al. European Journal of Combinatorics 102 (2022) 103505 Of course, different decorations may give different polynomials, but we denote the whole family of them with the same symbol DG, hoping that this ambiguity will not cause too much confusion. 2.2. Combinatorial Nullstellensatz For a monomial M, let degxi(M) denote the degree of the variable xiin M. The total degree of the monomial Mis the sum ∑n i=1degxi(M). In a graph polynomial each monomial has the same total degree equal to the number of edges of G. Recall that the degree of a polynomial is the maximum of total degrees of its non-vanishing monomials. We will use the following famous theorem of Alon [2]. Theorem 2 (Combinatorial Nullstellensatz, [2]).Let P be a polynomial in F[x1,x2,...,xn], where Fis an arbitrary field of coefficients. Suppose that there is a non-vanishing monomial xk1 1xk2 2···xkn nin P whose total degree is equal to the degree of P. Then, for arbitrary sets Ai⊆F, with |Ai| = ki+1, there exist elements ai∈Aisuch that P(a1,a2,...,an)= 0. In view of this theorem it is convenient to denote by AF(P) the least integer ksuch that the polynomial Phas a non-vanishing monomial Mwhose degree is equal to the degree of Pand satisfying degxi(M)⩽k, for each i=1,2,...,n. Let D1,D2be any two orientations of the graph Gsharing the same in-degree sequence. Observe that the set of edges oriented differently in D1than in D2is an Eulerian subgraph of both D1and D2. Thus, every monomial corresponding to an acyclic orientation of Gis of multiplicity exactly 1 in MG. Such monomials are non-vanishing in PG, and AF(PG) is well defined for every graph G. For the decorated graph polynomial DG, which denotes a collection of polynomials, we define AF(DG) as the least number ksuch that AF(P)⩽kholds for every Pin DG. It is not hard to demonstrate that for every graph Gwe have AF(PG)⩽AF(DG)⩽col(G)−1, where col(G) is the coloring number of G, defined as the least ksuch that the vertices of Gcan be linearly ordered so that each vertex vhas at most k−1 neighbors that precede vin the ordering. 2.3. Field coloring and graph polynomials Let Fbe any field and let ℓbe any edge labeling of a graph Gby the elements of F. Let DGbe a decorated graph polynomial with some fixed decoration over F. Consider the polynomial DG,ℓ defined as: DG,ℓ(x1,x2,...,xn)=∏ e=xixj∈E(G) (aexi+bexj+ℓ(e)).(2.3) Our basic observation is formulated as follows. Theorem 3. Let G be any simple graph, with a graph polynomial PG, and let Fbe an arbitrary field. Let ℓbe any edge labeling of G by the elements of F. Then AF(DG,ℓ)=AF(DG). Proof. First notice that the polynomial DG,ℓ can be written as: DG,ℓ =DG+Q,(2.4) where Qis a polynomial of degree strictly smaller than the degree of DG. Indeed, we obtain the summand DGby choosing the whole expression (aexi+bexj) in every factor of DG,ℓ. In every other case, the formed monomial uses at least one constant ℓ(e), hence the total degree of such monomial is strictly smaller than the number of edges of G, which is equal to the degree of DG. This means that every non-vanishing monomial of DGdoes not vanish in DG,ℓ. This completes the proof. □ 3 B. Bosek, J. Grytczuk, G. Gutowski et al. European Journal of Combinatorics 102 (2022) 103505 2.4. Field coloring of planar graphs In [21] Zhu proved that every planar graph Gsatisfies AQ(PG)⩽4, though the same proof works for an arbitrary field. This constitutes an algebraic analog of the famous result of Thomassen [16] on 5-choosability of planar graphs. We will derive below a slightly stronger statement. Theorem 4. Let G be a planar graph and let DGbe its decorated graph polynomial over an arbitrary field F. Then AF(DG)⩽4. By Theorems 3 and 4we get immediately the following result. Corollary 1. Every planar graph is F-5-choosable, where Fis an arbitrary field with at least 5elements. The original proof from [21] is by induction with the same scenario as in Thomassen’s famous proof from [16], except for one unexpected twist. We will give below a purely algebraic proof along similar lines of the following more general statement, stressing the fact that it works for decorated polynomials over an arbitrary field (which is crucial for our applications). Theorem 5. Let G be a near-triangulation and let e =xy be an arbitrary edge of the boundary cycle of G. Then a decorated graph polynomial DG−eover an arbitrary field Fcontains a non-vanishing monomial M satisfying the following conditions: (i) degx(M)=degy(M)=0, (ii) degv(M)⩽2, for every boundary vertex v, (iii) degu(M)⩽4, for every interior vertex u. Before we present the proof, let us comment on how Theorem 4 is derived from Theorem 5. We can choose any planar drawing of a planar graph G, and any edge e=xy of the boundary cycle of the drawing. Let Mbe the non-vanishing monomial in DG−egiven by Theorem 5, and observe that the monomial Mx does not vanish in DGand certifies that AF(DG)≤4. Proof of Theorem 5.Let us denote P=DG−e, and call a non-vanishing monomial Min Psatisfying conditions (i)–(iii), a nice monomial for (G,e). We use induction on the number of vertices of G. It is easy to check that G=K3, a complete graph on vertex set {x,y, v}, satisfies the assertion. In this case we have DG−e=(a1x+b1v)(a2y+b2v), and the only nice monomial is M=v2, whose coefficient is b1b2= 0. Hence, Mis non-vanishing. We distinguish two cases. Case 1. The boundary cycle of Ghas a chord. Suppose first that Ghas a chord f=wz. This chord splits Ginto two subgraphs G1and G2. We assume that eis in G1, while fbelongs to both subgraphs. By induction we assume that both graphs contain nice non-vanishing monomials M1and M2for (G1,e) and (G2,f), respectively. Let us denote P1=DG1−e, and P2=DG2−f. Then we have P=P1P2, and we see that the monomial M=M1M2appears in the expansion of P. We claim that Mis a nice monomial for (G,e). It is easy to see that Msatisfies conditions (i)–(iii). To see that it is non-vanishing, notice that M=M1M2 is the only way of expressing the monomial Mas a product of two monomials from P1and P2, respectively. This is because the only common variables of P1and P2are wand z, and they do not occur in M2. This shows that cM(P)=cM1(P1)·cM2(P2)= 0, confirming that Mis non-vanishing in the polynomial P. 4 B. Bosek, J. Grytczuk, G. Gutowski et al. European Journal of Combinatorics 102 (2022) 103505 Case 2. The boundary cycle of Ghas no chord. Suppose that there is no chord in G. Let v= xbe the neighbor of yon the boundary of G. Let tbe the other neighbor of von the outer face, and let x1,x2,...,xkbe the neighbors of vlying in the interior of G. Let G′=G−v. By the inductive assumption, there is a nice monomial M′for (G′,e) in the graph polynomial P′=DG′−e. So, we have cM′(P′)= 0. Subcase 1. The boundary face is a triangle. Suppose first that t=x, which means that the boundary face is a triangle. In this case the nice monomial M′has the form M′=Yxr1 1xr2 2. . . xrk k, where ri⩽2 for each i=1,2,...,k, and Yis a monomial consisting of the rest of the variables. Since M′is nice for (G′,e), the monomial Ydoes not contain variables xand y, and each other variable zin Ysatisfies degz(Y)⩽4. First notice that P=P′Q, where Q=(av+bx)(cv+dy)(a1v+b1x1)(a2v+b2x2). . . (akv+bkxk). In the expansion of Qwe get the monomial N=v2x1. . . xk, whose coefficient is cN(Q)=acb1···bk= 0. Hence, in the expansion of the product P′Qwe get the monomial M=M′N, which can be written as M=Yxr1+1 1xr2+1 2. . . xrk+1 kv2. Clearly Msatisfies conditions (i)–(iii). We claim that it is also non-vanishing in P. More specifically, we claim that there is only one way of expressing Mas a product M=AB of two monomials, with Afrom P′and Bfrom Q. Indeed, to get v2in Bwe have to use the first two factors of Q, since otherwise we have xor yin M. This implies that B=Nand A=M′. Thus cM(P)=cM′(P′)·cN(Q)= 0, which shows that Mis non-vanishing in P. For the remaining subcases, we assume that t= x. Subcase 2. There is a special monomial. Suppose first that there exists a non-vanishing special monomial Sin P′which satisfies all conditions (i)–(iii), except that degt(S)⩽1 and degxi(S)⩽3 for at most one i. We may assume without loss of generality that i=1. So, we assume that cS(P′)= 0. This special monomial Scan be written in the form S=Zxs1 1xs2 2. . . xsk kts, where s⩽1, s1⩽3, si⩽2 for i=2,3, . . . k, and Zis some monomial consisting of the rest of the variables. As before we may write the polynomial P=DG−eas the product P=P′Qwith Q=(av+by)(cv+dt)(a1v+b1x1). . . (akv+bkxk). In the expansion of Qwe get the monomial N′=vtx1. . . xk, with coefficient cN′(Q)=adb1···bk= 0. Hence, in the expansion of the product P′Qwe get the monomial M=SN′, which can be written as M=Zxs1+1 1xs2+1 2. . . xsk+1 kts+1v. 5 B. Bosek, J. Grytczuk, G. Gutowski et al. European Journal of Combinatorics 102 (2022) 103505 Clearly, Msatisfies conditions (i)–(iii). Also, as in the previous case, the splitting M=SN′is unique. Indeed, assume that M=AB is any decomposition of Minto the product of monomials from P′and Q, respectively. To get vin Bwe have to use the first factor of Q, since otherwise we have yin M. This already implies that B=N′and A=S. Hence, cM(P)=cS(P′)·cN′(Q)= 0, so, Mis non-vanishing in P. Subcase 3. There is no special monomial. Finally, assume that there is no special monomial in P′. However, by inductive assumption, there is still a nice non-vanishing monomial M′in the graph polynomial P′=DG′−e. This monomial can be written now as M′=Yxr1 1xr2 2. . . xrk ktr, where r⩽2, ri⩽2, for all i=1,2,...,k, and Yis a monomial consisting of the rest of the variables. As in Subcase 1, we have P=P′Q, where Q=(av+by)(cv+dt)(a1v+b1x1)(a2v+b2x2). . . (akv+bkxk). In the expansion of Qwe get the monomial N=v2x1. . . xk, with cN(Q)=acb1···bk= 0. Hence, in the expansion of the product P′Qwe get the monomial M=M′N, which can be written as M=Yxr1+1 1xr2+1 2. . . xrk+1 ktrv2. Clearly Msatisfies conditions (i)–(iii). We claim that there is only one way of expressing Mas a product of two monomials, M=AB, with Afrom P′and Bfrom Q. Indeed, to get v2in Bwe have to choose variable vexactly twice from the factors of Q. The first choice must be from the first factor, otherwise yappears in M. The second choice must be from the second factor, since otherwise the variable tappears in B, while some xiis missing. Then, in order to get M=AB, we would have to have tr−1and xri+1 iin the monomial A. But then Ais a special monomial in P′, contrary to our assumption. Hence, we must have B=Nand A=M′. Thus cM(P)=cM′(P′)·cN(Q)= 0, which demonstrates that Mis non-vanishing in P. The proof is complete. □ In [8] Grytczuk and Zhu proved that every planar graph Gcontains a matching Ssuch that AF(PG−S)⩽3. The proof is similar to the above and can be easily modified to give the following result. Theorem 6. Every planar graph G contains a matching S such that AF(DG−S)⩽3, for an arbitrary field F. Thus, G −S is F-4-choosable, and in particular, Z2×Z2-colorable. 2.5. K5-minor-free graphs To extend the above results to graphs without a K5-minor we will use the well-known characterization theorem of Wagner [18]. A similar approach was taken by Abe, Kim, and Ozeki [1] in an extension of the result of Zhu [21] to graphs with no K5-minor. Recall that a k-clique-sum of two graphs is a new graph obtained by gluing the two graphs along a clique of size kin each of them, and possibly deleting some edges of the clique. Recall also that the Wagner graph V8is the graph obtained from the cycle C8by adding four edges joining antipodal pairs of vertices. 6 B. Bosek, J. Grytczuk, G. Gutowski et al. European Journal of Combinatorics 102 (2022) 103505 Theorem 7 (Wagner, [18]).Every edge-maximal graph without a K5-minor can be built recursively from planar triangulations and the graph V8by clique-sums with cliques on at most 3vertices. We need the following result. Theorem 8. Let G be a plane triangulation and let T be any triangle in G. Then the decorated graph polynomial DG−E(T)over an arbitrary field Fcontains a non-vanishing monomial N such that degu(N)=0, for every vertex u ∈V(T), and degw(N)⩽4, for all other vertices. Proof. Let V(T)= {x,y, v}and denote e=xy. Suppose first that Tis a facial triangle. We may assume that Tis the outer face of G.ByTheorem 5 we know that there is a non-vanishing monomial Min DG−esuch that degx(M)=degy(M)=0, degv(M)⩽2, and degw(M)⩽4, for all other variables. In order to form this monomial we have to pick vexactly twice; once from each factor, (ax +bv) and (cy +dv), since we can choose neither x, nor y. Thus, when we delete the corresponding two edges xvand yvfrom the graph G−e, we must have a non-vanishing monomial N=M/v2in the polynomial DG−E(T). If Tis not a facial triangle, then we may split the triangulation Ginto two sub-triangulations, G1 and G2, lying inside and outside the triangle T, respectively. Then we may apply the same argument to each sub-triangulation separately to get the desired monomials N1and N2in polynomials DG1−E(T) and DG2−E(T), respectively. Clearly, we have DG−E(T)=DG1−E(T)DG2−E(T), and it is easy to see that N=N1N2is a non-vanishing monomial in DG−E(T)satisfying the assertion of the theorem. □ Now we may give the proof of the aforementioned extension of Theorem 4. Theorem 9. Let G be a graph without a K5-minor and let DGbe its decorated graph polynomial over an arbitrary field F. Then AF(DG)⩽4. Proof. Let Gbe an edge-maximal K5-minor-free graph. We proceed by induction on the number of terms in a clique-sum giving G. So, suppose that Gis k-clique-sum, k⩽3, of two graphs Hand F, where His a clique-sum with a smaller number of terms, while Fis a plane triangulation or F=V8. Assume by induction that AF(DH)⩽4, and let Mbe the monomial witnessing this inequality with coefficient cM(DH)= 0. In the triangulation case, let {x,y,z}be the three vertices of the common triangle Tin Hand F. Let Nbe a monomial in DF−E(T)guaranteed by Theorem 8 with coefficient cN(DF−E(T))= 0. We claim that the monomial MN occurs in the polynomial DGwith coefficient cMN (DG)=cM(DH)·cN(DF−E(T)). Indeed, we have an obvious equality DG=DHDF−E(T)and the only common variables of the two polynomial factors are x,y,z, none of which appears in the monomial N. If F=V8, then the reasoning is similar. Notice that V8is triangle-free, so the clique-sum can be made on one vertex or one edge. Suppose it is the latter situation (the former is even easier). Let x,ybe the two common vertices of Hand F. It is enough to notice that for every edge e=xy of V8there is an acyclic orientation of V8−ewith in-degrees of both vertices xand yequal to 0. The monomial Jcorresponding to this orientation has a non-zero coefficient, the variables xand ydo not occur in J, while other variables have degrees at most 3. Thus, as before we have cMJ (DG)=cM(DH)·cJ(DF−e)= 0. This completes the proof. □ By Theorems 9 and 3we get immediately the following results, whose special case extends Z5-colorability of planar graphs. Corollary 2. Let Fbe an arbitrary field with at least 5elements. Then every graph G without a K5-minor is F-5-choosable. 7 B. Bosek, J. Grytczuk, G. Gutowski et al. European Journal of Combinatorics 102 (2022) 103505 2.6. Extending to cyclic group choosability The polynomial method is tied to an ambient field. One way of extending the potential results to cyclic groups is to use cyclic subgroups of multiplicative groups of fields with appropriate order and to express the conditions on the coloring using multiplication instead of addition. By this trick we get the following result. Theorem 10. Let Γbe an arbitrary cyclic group of order at least 5. Then every K5-minor free graph G is Γ-5-choosable. Proof. Let Γbe a (multiplicative) cyclic group of order m⩾5. Let pbe a prime number such that gcd(m,p)=1. Consider the field F=Fpφ(m). Its multiplicative group F∗is the cyclic group of order pφ(m)−1. Since mdivides pφ(m)−1 (by Euler’s theorem), Γis a subgroup of F∗. Let ℓbe a labeling of the edges of a graph Gby the elements of Γ. Denote by ℓij =ℓ(xixj) the label of an edge xixjin G. For any fixed orientation  Gof G, let dibe the in-degree of the vertex xi. Consider now the following function fG(x1,x2,...,xn)=∏ (xi,xj)∈E( G) (xix−1 j−ℓij)=1 ∏n i=1xdi i ∏ (xi,xj)∈E( G) (xi−ℓijxj). By Theorem 9, the polynomial PG(x1,x2,...,xn)=∏ (xi,xj)∈E( G) (xi−ℓijxj) has a nonvanishing monomial of degree at most four. It follows that, for every collection of sets A1,A2,...,An⊆Γ⊆F∗, each with cardinality at least five, there is a point (a1,a2,...,an) in A1×A2×···×Anwhere PGis not vanishing, which implies that fG(a1,a2,...,an)= 0. It follows that (a1,a2,...,an) is a Γ-coloring of Gfor the labeling ℓ.□ 2.7. The number of colorings In this section we prove the second part of Theorem 1. Our main tool is the following general result of Alon and Füredi [3]. Theorem 11 (Alon and Füredi, [3]).Let Fbe an arbitrary field, let A1,A2,...,Anbe any non-empty subsets of F, and let B =A1×A2× ··· × An. Suppose that P(x1,x2,...,xn)is a polynomial over F that does not vanish on all of B. Then, the number of points in B for which P has a non-zero value is at least min∏n i=1qi, where the minimum is taken over all integers qisuch that 1⩽qi⩽|Ai|and ∑n i=1qi⩾∑n i=1|Ai|−degP. For a convenient use of this result, and for the sake of completeness, we will prove a slightly weaker statement by an argument resembling a beautiful proof of Combinatorial Nullstellensatz, due to Michałek [13]. A similar approach was taken by Bishnoi, Clark, Potukuchi, and Schmitt [4] to get some generalization of the Alon-Füredi theorem. We need a simple technical lemma. Lemma 1. Let a1,a2,...,anbe positive integers, with maxai=t⩾2and ∑n i=1ai=S. Then A= n ∏ i=1 ai⩾tS−n t−1.(2.5) Proof. The proof is by induction on n. For n=1 we have A=a1=tand S=a1=t, hence we get equality in (2.5). For n⩾2, let ai0=min ai=m. Then, by the inductive assumption, we have A ai0=A m⩾t(S−m)−(n−1) t−1. 8 B. Bosek, J. Grytczuk, G. Gutowski et al. European Journal of Combinatorics 102 (2022) 103505 Observe that for every x∈ [1,t]we have x⩾tx−1 t−1.(2.6) Indeed, it is not hard to check that the function f(x)=t(x−1)/(t−1) is convex, with f(1) =1 and f(t)=t. Hence, taking x=m, we may write A⩾m·t(S−m)−(n−1) t−1⩾tm−1 t−1·t(S−m)−(n−1) t−1=tS−n t−1, as asserted. □ Theorem 12. Let Fbe an arbitrary field, and let A1,A2,...,Anbe any non-empty subsets of F, with S=∑n i=1|Ai|and t =max|Ai|. Let B =A1×A2×··· × Anand suppose that P(x1,x2,...,xn)is a polynomial over Fof degree deg P=d, that does not vanish on all of B. Then, the number of points in B for which P has a non-zero value is at least tS−n−d t−1, provided that S ⩾n+d and t ⩾2. Proof. The proof is by induction on dand n. If d=0, then Pequals some non-zero constant c∈F, and therefore all points of Bare non-vanishing for P. There are exactly ∏n i=1|Ai|of them, so, the assertion follows from Lemma 1 by putting ai= |Ai|. For n=1 and arbitrary d⩾1, we know that the number of roots of a polynomial Pis at most d. Hence, the number of elements of A1for which Pis non-zero is at least t−d. So, by the assumption that t⩾d+1 and the inequality (2.6), we have t−d⩾tt−1−d t−1=tS−1−d t−1, as S=tin this case. Assume now that d⩾1 and n⩾2. Let |A1| = j, and assume, without loss of generality, that there is another set Ai, with |Ai| = t. Let b∈A1be any element, and let us divide the polynomial P by (x1−b): P=(x1−b)Qb+Rb. Observe that degQb=degP−1=d−1, degRb⩽d, and that the polynomial Rbdoes not contain the variable x1. Suppose first that the polynomial Rbvanishes at all points of the grid A2×···×An. This implies that j⩾2, since otherwise, the polynomial Pwould vanish over the whole grid B, contrary to the assumption. Furthermore, each non-vanishing point of Pin Bis at the same time a non-vanishing point of Qbin the grid (A1−b)×A2×···×An, and vice versa. Thus, by the inductive assumption we get that Phas at least t(S−1)−n−(d−1) t−1=tS−n−d t−1 non-vanishing points in B. Finally, suppose that for every b∈A1, the polynomial Rbhas some non-vanishing points in the grid A2×···×An. Then each such point can be extended to a non-vanishing point of Pby setting x1=b. By the inductive assumption on n, the number of such points for each Rbis at least t(S−j)−(n−1)−d t−1. Hence, the total number of non-vanishing points of Pin the grid Bis at least j·t(S−j)−(n−1)−d t−1⩾tj−1 t−1·t(S−j)−(n−1)−d t−1=tS−n−d t−1, by the inequality (2.6). The proof is complete. □ The above result and Theorem 9 easily imply the following corollary. 9