On the density of sets of vectors

Noga Alon

doi:10.1016/0012-365X(83)90253-4

On the density of sets of vectors

Noga Alon

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

54 Scopus citations

Abstract

Answering a question of Erdös, Sauer [4] and independently Perles and Shelah [5] found the maximal cardinality of a collection F of subsets of a set: N of cardinality n such that for every subset M ⊂ N of cardinality m |{C ∩ M: C ε{lunate} F}| < 2^m. Karpovsky and Milman [3] generalised this result. Here we give a short proof of these results and further extensions.

Original language	English (US)
Pages (from-to)	199-202
Number of pages	4
Journal	Discrete Mathematics
Volume	46
Issue number	2
DOIs	https://doi.org/10.1016/0012-365X(83)90253-4
State	Published - 1983
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0012-365X(83)90253-4

Cite this

@article{dcc84ec21c3f47afad810608cef1fa46,

title = "On the density of sets of vectors",

abstract = "Answering a question of Erd{\"o}s, Sauer [4] and independently Perles and Shelah [5] found the maximal cardinality of a collection F of subsets of a set: N of cardinality n such that for every subset M ⊂ N of cardinality m |{C ∩ M: C ε{lunate} F}| < 2m. Karpovsky and Milman [3] generalised this result. Here we give a short proof of these results and further extensions.",

author = "Noga Alon",

year = "1983",

doi = "10.1016/0012-365X(83)90253-4",

language = "English (US)",

volume = "46",

pages = "199--202",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - On the density of sets of vectors

AU - Alon, Noga

PY - 1983

Y1 - 1983

N2 - Answering a question of Erdös, Sauer [4] and independently Perles and Shelah [5] found the maximal cardinality of a collection F of subsets of a set: N of cardinality n such that for every subset M ⊂ N of cardinality m |{C ∩ M: C ε{lunate} F}| < 2m. Karpovsky and Milman [3] generalised this result. Here we give a short proof of these results and further extensions.

AB - Answering a question of Erdös, Sauer [4] and independently Perles and Shelah [5] found the maximal cardinality of a collection F of subsets of a set: N of cardinality n such that for every subset M ⊂ N of cardinality m |{C ∩ M: C ε{lunate} F}| < 2m. Karpovsky and Milman [3] generalised this result. Here we give a short proof of these results and further extensions.

UR - http://www.scopus.com/inward/record.url?scp=0001604527&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0001604527&partnerID=8YFLogxK

U2 - 10.1016/0012-365X(83)90253-4

DO - 10.1016/0012-365X(83)90253-4

M3 - Article

AN - SCOPUS:0001604527

SN - 0012-365X

VL - 46

SP - 199

EP - 202

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

ER -

On the density of sets of vectors

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this