Independent Finite Sums for K_m-free Graphs
by
Neil Hindman
Howard University
Coauthors: Walter Deuber (Howard University), David Gunderson (Howard University), Dona Strauss (Hull University)

Recently, in conversation with Erdos, Hajnal asked whether for each triangle free graph G with vertices in N, there must exist a sequence <x_n >_{n = 1}^\infty so that whenever F and H are distinct finite nonempty subsets of N, { \Sigma_{n in F} x_n, \Sigma_{n in H} x_n } is not an edge of G. (That is, FS(<x_n >_n=1^\infty) is an independent set.) In this paper we answer this question in the negative. We also show that if one replaces the assumption that G is triangle free by the assertion that G contains no complete bipartite graph on two sets of size m >= 2 , the conclusion does hold. And we show that if for some m >= 3, G contains no K_m, then there must exist a sequence <x_n >_{n = 1}^\infty so that whenever F and H are disjoint finite nonempty subsets of N, { \Sigma_{n in F} x_n, \Sigma_{n in H} x_n } is not an edge of G. The counterexample is purely combinatorial, while the positive results utilize the algebraic structure of the semigroup (\betaN, +) . (Surprise, surprise!)

Date received: May 31, 1996

Copyright © 1996 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caag-13.