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.
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
NERFINISHED
ⓘ
Sperner system NERFINISHED ⓘ antichain ⓘ |
| appearsIn | Sperner’s 1928 paper on subsets of a finite set NERFINISHED ⓘ |
| centralResult | Sperner theorem NERFINISHED ⓘ |
| 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 NERFINISHED ⓘ |
| optimizationQuestion | determine maximum size for given ground set size ⓘ |
| posetView | antichain in the poset (2^[n], subseteq) ⓘ |
| relatedConcept |
Boolean lattice
ⓘ
Dilworth theorem NERFINISHED ⓘ Erdos–Ko–Rado theorem NERFINISHED ⓘ LYM inequality NERFINISHED ⓘ antichain in a partially ordered set ⓘ chain decomposition ⓘ |
| relatedInequality | Lubell–Yamamoto–Meshalkin inequality NERFINISHED ⓘ |
| specialCaseOf | Sperner poset NERFINISHED ⓘ |
| 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 NERFINISHED ⓘ information theory ⓘ probabilistic combinatorics ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.