Sperner family

E518470

A Sperner family is a collection of subsets of a finite set in which no subset is contained within another, central in extremal set theory and combinatorics.

All labels observed (9)

How this entity was disambiguated

Statements (48)

Predicate Object
instanceOf antichain of sets ⓘ
combinatorial concept ⓘ
set system ⓘ
achievesMaximumWhen family consists of all k-subsets with k = ceil(n/2) ⓘ
family consists of all k-subsets with k = floor(n/2) ⓘ
alsoKnownAs Sperner collection ⓘ
linked to: Sperner family

Sperner system ⓘ
linked to: Sperner family

antichain ⓘ
appearsIn Sperner’s 1928 paper on subsets of a finite set ⓘ
linked to: Sperner family
centralResult Sperner theorem ⓘ
linked to: Sperner family
constraintType inclusion-free condition ⓘ
countingProblem enumerate number of Sperner families on an n-element set ⓘ
definedOn finite set ⓘ
field combinatorics ⓘ
extremal set theory ⓘ
generalizationOf antichain in any poset ⓘ
groundSetCardinality finite ⓘ
hasVariant k-Sperner family ⓘ
multiset Sperner family ⓘ
vector Sperner family ⓘ
isClosedUnder no nontrivial closure operations implied by definition ⓘ
keyProperty no set in the family is a subset of another set in the family ⓘ
the family is an antichain under set inclusion ⓘ
mathematicalObjectType family of subsets ⓘ
maximalityConcept maximal Sperner family ⓘ
maxSizeOnNElementSet binomial(n, floor(n/2)) ⓘ
namedAfter Emanuel Sperner ⓘ
optimizationQuestion determine maximum size for given ground set size ⓘ
posetView antichain in the poset (2^[n], subseteq) ⓘ
relatedConcept Boolean lattice ⓘ
Dilworth theorem ⓘ
Erdos–Ko–Rado theorem ⓘ
LYM inequality ⓘ
antichain in a partially ordered set ⓘ
chain decomposition ⓘ
relatedInequality Lubell–Yamamoto–Meshalkin inequality ⓘ
specialCaseOf Sperner poset ⓘ
linked to: Sperner family
structure subset of the Boolean lattice ordered by inclusion ⓘ
studies maximal size of antichains in the Boolean lattice ⓘ
subsetCondition for all A,B in the family, A not subset of B and B not subset of A ⓘ
typicalNotation F subset of 2^[n] ⓘ
typicalUniverse power set of an n-element set ⓘ
underlyingRelation set inclusion ⓘ
usedIn coding theory ⓘ
design theory ⓘ
extremal combinatorics ⓘ
information theory ⓘ
probabilistic combinatorics ⓘ

How these facts were elicited

Referenced by (12)

Full triples — surface form annotated when it differs from this entity's canonical label.

Sperner's lemma → relatedTo → Sperner family ⓘ
Emanuel Sperner → familyName → Sperner ⓘ
linked to: Sperner family
Emanuel Sperner → notableWork → Sperner's theorem ⓘ
linked to: Sperner family
Emanuel Sperner → notableConcept → Sperner family ⓘ
Emanuel Sperner → notableConcept → Sperner's theorem ⓘ
linked to: Sperner family
Sperner family → alsoKnownAs → Sperner system ⓘ
linked to: Sperner family
Sperner family → alsoKnownAs → Sperner collection ⓘ
linked to: Sperner family
Sperner family → centralResult → Sperner theorem ⓘ
linked to: Sperner family
Sperner family → specialCaseOf → Sperner poset ⓘ
linked to: Sperner family
Sperner family → appearsIn → Sperner’s 1928 paper on subsets of a finite set ⓘ
linked to: Sperner family
Erdős–Ko–Rado theorem → relatedTo → Sperner's theorem ⓘ
linked to: Sperner family
Dedekind number → relatedConcept → Sperner’s theorem ⓘ
linked to: Sperner family