Non-averaging Subsets and Non-vanishing Transversals

Noga Alon, Imre Z. Ruzsa

Research output: Contribution to journalArticle

8 Scopus citations

Abstract

It is shown that every set ofnintegers contains a subset of sizeΩ(n1/6) in which no element is the average of two or more others. This improves a result of Abbott. It is also proved that for everyε>0 and everym>m(ε) the following holds. IfA1,...,Amaremsubsets of cardinality at leastm1+εeach, then there area1∈A1,...,am∈Amso that the sum of every nonempty subset of the set {a1,...,am} is nonzero. This is nearly tight. The proofs of both theorems are similar and combine simple probabilistic methods with combinatorial and number theoretic tools.

Original languageEnglish (US)
Pages (from-to)1-13
Number of pages13
JournalJournal of Combinatorial Theory. Series A
Volume86
Issue number1
DOIs
StatePublished - Apr 1 1999
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Non-averaging Subsets and Non-vanishing Transversals'. Together they form a unique fingerprint.

Cite this