Non-averaging Subsets and Non-vanishing Transversals

Noga Alon; Imre Z. Ruzsa

doi:10.1006/jcta.1998.2926

Non-averaging Subsets and Non-vanishing Transversals

Noga Alon
, Imre Z. Ruzsa

Research output: Contribution to journal › Article › peer-review

13 Scopus citations

Abstract

It is shown that every set ofnintegers contains a subset of sizeΩ(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 everym>m(ε) the following holds. IfA₁,...,A_maremsubsets of cardinality at leastm^1+εeach, then there area₁∈A₁,...,a_m∈A_mso that the sum of every nonempty subset of the set {a₁,...,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.

Original language	English (US)
Pages (from-to)	1-13
Number of pages	13
Journal	Journal of Combinatorial Theory. Series A
Volume	86
Issue number	1
DOIs	https://doi.org/10.1006/jcta.1998.2926
State	Published - Apr 1999
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1006/jcta.1998.2926

Cite this

@article{5de0e89633cc4c77a7afd519ea199f93,

title = "Non-averaging Subsets and Non-vanishing Transversals",

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.",

author = "Noga Alon and Ruzsa, \{Imre Z.\}",

note = "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.",

year = "1999",

month = apr,

doi = "10.1006/jcta.1998.2926",

language = "English (US)",

volume = "86",

pages = "1--13",

journal = "Journal of Combinatorial Theory. Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

number = "1",

}

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 - https://www.scopus.com/pages/publications/0009917149

UR - https://www.scopus.com/pages/publications/0009917149#tab=citedBy

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 -

Non-averaging Subsets and Non-vanishing Transversals

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this