INDEPENDENT FINITE SUMS FOR K-M-FREE GRAPHS

Recently, in conversation with Erdos, Hajnal asked whether or not for any triangle-free graph G on the vertex set N, there always exists a s equence [x(n)](n=1)(infinity), so that whenever F and H are distinct f inite nonempty subsets of N, {Sigma(n is an element of F)x(n), Sigma(n is an element of H)x(n)} is not an edge of G (that is, FS([x(n)](n=1) (infinity)) is an independent set). We answer this question in the neg ative. We also show that if one replaces the assumption that G is tria ngle-Free by the assertion that for some in, G contains no complete bi partite graph K-m,K-m then the conclusion does hold. If for some m gre ater than or equal to 3, G contains no K-m, we show there exists a seq uence [x(n)](n=1)(infinity), so that whenever F and H are disjoint fin ite nonempty subsets of N, {Sigma(n is an element of F)x(n), Sigma(n i s an element of H)x(n)} is not an edge of G. Both of the affirmative r esults are in fact valid for a graph G on an arbitrary cancellative se migroup (S, +). (C) 1997 Academic Press.