As a generalization of the concept of Sidon sets, a set of real numbers is called a (4, 5)-set if every four-element subset determines at least five distinct differences. Let g(n) be the largest number such that any n-element (4,5)-set contains a g(n)-element Sidon set (i.e., a subset 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 lower bound whose proof is based on a Turan-type theorem obtained for sparse 3-uniform hypergraphs associated with (4, 5)-sets. (C) 1995 Academic Press, Inc. [References: 6]
展开▼