An Application of Graph Theory to Additive Number Theory

Noga Alon, P. Erdös

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

A sequence of integers A = {a1 < a2 < ⋯ < an} is a Bk2 sequence if the number of representations of every integer as the sum of two distinct ais is at most k. In this note we show that every Bk2 sequence of n terms is a union of ck2 · n1/3B12 sequences, and that there is a Bk2 sequence of n terms which is not a union of ck1 · c1/3B12 sequences. This solves a problem raised in [3, 4]. Our proof uses some results from extremal graph theory. We also discuss some related problems and results.

Original languageEnglish (US)
Pages (from-to)201-203
Number of pages3
JournalEuropean Journal of Combinatorics
Volume6
Issue number3
DOIs
StatePublished - 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'An Application of Graph Theory to Additive Number Theory'. Together they form a unique fingerprint.

Cite this