TY - JOUR
T1 - Non-averaging Subsets and Non-vanishing Transversals
AU - Alon, Noga
AU - Ruzsa, Imre Z.
N1 - Funding Information:
* Research supported in part by a State of New Jersey grant, by a United States Israeli BSF grant, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. -Research supported in part by the Hungarian National Foundation for Scientific Research, Grant Nos. 17433 and 25617.
PY - 1999/4
Y1 - 1999/4
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0009917149&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0009917149&partnerID=8YFLogxK
U2 - 10.1006/jcta.1998.2926
DO - 10.1006/jcta.1998.2926
M3 - Article
AN - SCOPUS:0009917149
SN - 0097-3165
VL - 86
SP - 1
EP - 13
JO - Journal of Combinatorial Theory. Series A
JF - Journal of Combinatorial Theory. Series A
IS - 1
ER -