- Title
- Maximal antichains of minimum size
- Creator
- Kalinowski, Thomas; Leck, Uwe; Roberts, Ian T.
- Relation
- Electronic Journal of Combinatorics Vol. 20, Issue 2, p. 1-14
- Relation
- http://www.combinatorics.org/ojs/index.php/eljc/issue/view/Volume20-2
- Publisher
- Electronic Journal of Combinatorics
- Resource Type
- journal article
- Date
- 2013
- Description
- Let n ⩾4 be a natural number, and let K be a set K⊆[n]:={1,2,...,n}. We study the problem of finding the smallest possible size of a maximal family A of subsets of [n] such that A contains only sets whose size is in K, and A⊈B for all {A,B}⊆A, i.e. A is an antichain. We present a general construction of such antichains for sets K containing 2, but not 1. If 3∈K our construction asymptotically yields the smallest possible size of such a family, up to an o(n²) error. We conjecture our construction to be asymptotically optimal also for 3∉K, and we prove a weaker bound for the case K={2,4}. Our asymptotic results are straightforward applications of the graph removal lemma to an equivalent reformulation of the problem in extremal graph theory, which is interesting in its own right.
- Subject
- extremal set theory; Sperner property; maximal antichains; flat antichains
- Identifier
- http://hdl.handle.net/1959.13/1295427
- Identifier
- uon:19022
- Identifier
- ISSN:1077-8926
- Language
- eng
- Full Text
- Reviewed
- Hits: 1131
- Visitors: 1409
- Downloads: 336
Thumbnail | File | Description | Size | Format | |||
---|---|---|---|---|---|---|---|
View Details Download | ATTACHMENT02 | Publisher version (open access) | 289 KB | Adobe Acrobat PDF | View Details Download |