Explicit construction of exponential sized families of k-independent sets

Research output: Contribution to journalArticlepeer-review

82 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)191-193
Number of pages3
JournalDiscrete Mathematics
Volume58
Issue number2
DOIs
StatePublished - Feb 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Explicit construction of exponential sized families of k-independent sets'. Together they form a unique fingerprint.

Cite this