LINEAR SETS WITH 5 DISTINCT DIFFERENCES AMONG ANY 4 ELEMENTS

As a generalization of the concept of Sidon sets, a set of real number s is called a (4, 5)-set if every four-element subset determines at le ast five distinct differences. Let g(n) be the largest number such tha t any n-element (4,5)-set contains a g(n)-element Sidon set (i.e., a s ubset of g(n) elements with distinct differences). It is shown that (1 /2 + epsilon) n less than or equal to g(n) less than or equal to 3n/5 + 1, where epsilon is a positive constant. The main result is the lowe r bound whose proof is based on a Turan-type theorem obtained for spar se 3-uniform hypergraphs associated with (4, 5)-sets. (C) 1995 Academi c Press, Inc.