Non-averaging Subsets and Non-vanishing Transversals

✍ Scribed by Noga Alon; Imre Z Ruzsa

• Book ID: 102584132
• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 130 KB
• Volume: 86
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.1998.2926

✦ Synopsis

It is shown that every set of n integers contains a subset of size 0(n 1Â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 every m>m(=) the following holds. If A 1 , ..., A m are m subsets of cardinality at least m 1+= each, then there are a 1 # A 1 , ..., a m # A m so that the sum of every nonempty subset of the set [a 1 , ..., a m ] is nonzero. This is nearly tight. The proofs of both theorems are similar and combine simple probabilistic methods with combinatorial and number theoretic tools.