Explicit construction of exponential sized families of k-independent sets

N. Alon

doi:10.1016/0012-365X(86)90161-5

Explicit construction of exponential sized families of k-independent sets

N. Alon

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

85 Scopus citations

Abstract

Error correcting codes are used to describe explicit collections F_k of subsets of {1,2,...;n}, with |F_k| > 2^c_k·n (C_k > 0), such that for any selections A, B of k₂ and k₁ of members of F_k with k₁ + k₂ = k, there are elements in all the members of A and not in the members of B. This settles a problem of Kleitman and Spencer and a similar problem of Kleimman, Shearer and Sturtevant.

Original language	English (US)
Pages (from-to)	191-193
Number of pages	3
Journal	Discrete Mathematics
Volume	58
Issue number	2
DOIs	https://doi.org/10.1016/0012-365X(86)90161-5
State	Published - Feb 1986
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0012-365X(86)90161-5

Cite this

@article{6116b2cbcfa240ab8ca01fa2ed716828,

title = "Explicit construction of exponential sized families of k-independent sets",

abstract = "Error correcting codes are used to describe explicit collections Fk of subsets of \{1,2,...;n\}, with |Fk| > 2ck·n (Ck > 0), such that for any selections A, B of k2 and k1 of members of Fk with k1 + k2 = k, there are elements in all the members of A and not in the members of B. This settles a problem of Kleitman and Spencer and a similar problem of Kleimman, Shearer and Sturtevant.",

author = "N. Alon",

year = "1986",

month = feb,

doi = "10.1016/0012-365X(86)90161-5",

language = "English (US)",

volume = "58",

pages = "191--193",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Explicit construction of exponential sized families of k-independent sets

AU - Alon, N.

PY - 1986/2

Y1 - 1986/2

N2 - Error correcting codes are used to describe explicit collections Fk of subsets of {1,2,...;n}, with |Fk| > 2ck·n (Ck > 0), such that for any selections A, B of k2 and k1 of members of Fk with k1 + k2 = k, there are elements in all the members of A and not in the members of B. This settles a problem of Kleitman and Spencer and a similar problem of Kleimman, Shearer and Sturtevant.

AB - Error correcting codes are used to describe explicit collections Fk of subsets of {1,2,...;n}, with |Fk| > 2ck·n (Ck > 0), such that for any selections A, B of k2 and k1 of members of Fk with k1 + k2 = k, there are elements in all the members of A and not in the members of B. This settles a problem of Kleitman and Spencer and a similar problem of Kleimman, Shearer and Sturtevant.

UR - https://www.scopus.com/pages/publications/0000391239

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

U2 - 10.1016/0012-365X(86)90161-5

DO - 10.1016/0012-365X(86)90161-5

M3 - Article

AN - SCOPUS:0000391239

SN - 0012-365X

VL - 58

SP - 191

EP - 193

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

ER -

Explicit construction of exponential sized families of k-independent sets

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this