On sums of subsets of a set of integers

N. Alon, G. Freiman

Research output: Contribution to journalArticle

27 Scopus citations

Abstract

For r≧2 let p(n, r) denote the maximum cardinality of a subset A of N={1, 2,..., n} such that there are no B⊂A and an integer y with {Mathematical expression}b=yr. It is shown that for any ε>0 and n>n(ε), (1+o(1))21/(r+1)n(r-1)/(r+1)≦p(n, r)≦ne{open}+2/3 for all r≦5, and that for every fixed r≧6, p(n, r)=(1+o(1))·21/(r+1)n(r-1)/(r+1) as n→∞. Let f(n, m) denote the maximum cardinality of a subset A of N such that there is no B⊂A the sum of whose elements is m. It is proved that for 3 n6/3+e{open}≦m≦n2/20 log2n and n>n(ε), f(n, m)=[n/s]+s-2, where s is the smallest integer that does not divide m. A special case of this result establishes a conjecture of Erdo{combining double acute accent}s and Graham.

Original languageEnglish (US)
Pages (from-to)297-306
Number of pages10
JournalCombinatorica
Volume8
Issue number4
DOIs
StatePublished - Dec 1 1988
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Keywords

  • AMS subject classification (1980): 10A50, 10B35, 10J10

Fingerprint Dive into the research topics of 'On sums of subsets of a set of integers'. Together they form a unique fingerprint.

  • Cite this