Families of k-independent sets

Daniel J. Kleitman; Joel Spencer

doi:10.1016/0012-365X(73)90098-8

Families of k-independent sets

Daniel J. Kleitman, Joel Spencer

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

Abstract

A collection F of sets is k-independent if for any selections A, B of k₁ and k₂ of its members with k₁+k₂=k, there are elements in all the members of A and not in the members of B. Bounds on the maximal size of k-independent families exponential in the total number of elements are obtained.

Original language	English (US)
Pages (from-to)	255-262
Number of pages	8
Journal	Discrete Mathematics
Volume	6
Issue number	3
DOIs	https://doi.org/10.1016/0012-365X(73)90098-8
State	Published - 1973

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0012-365X(73)90098-8

Cite this

@article{a5c291a11f6e4ae6a6dce26eb7b4a186,

title = "Families of k-independent sets",

abstract = "A collection F of sets is k-independent if for any selections A, B of k1 and k2 of its members with k1+k2=k, there are elements in all the members of A and not in the members of B. Bounds on the maximal size of k-independent families exponential in the total number of elements are obtained.",

author = "Kleitman, {Daniel J.} and Joel Spencer",

note = "Funding Information: * Supported in part by ONR ** Present address Mthematics",

year = "1973",

doi = "10.1016/0012-365X(73)90098-8",

language = "English (US)",

volume = "6",

pages = "255--262",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Families of k-independent sets

AU - Kleitman, Daniel J.

AU - Spencer, Joel

N1 - Funding Information: * Supported in part by ONR ** Present address Mthematics

PY - 1973

Y1 - 1973

N2 - A collection F of sets is k-independent if for any selections A, B of k1 and k2 of its members with k1+k2=k, there are elements in all the members of A and not in the members of B. Bounds on the maximal size of k-independent families exponential in the total number of elements are obtained.

AB - A collection F of sets is k-independent if for any selections A, B of k1 and k2 of its members with k1+k2=k, there are elements in all the members of A and not in the members of B. Bounds on the maximal size of k-independent families exponential in the total number of elements are obtained.

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

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

U2 - 10.1016/0012-365X(73)90098-8

DO - 10.1016/0012-365X(73)90098-8

M3 - Article

AN - SCOPUS:0000294926

SN - 0012-365X

VL - 6

SP - 255

EP - 262

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 3

ER -

Families of k-independent sets

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this