Abstract
Let 𝑛 ≥ 4 be a natural number, and let 𝐾 be a set 𝐾 ⊆ [𝑛] := {1, 2, . . . , 𝑛}. We study the problem to find the smallest possible size of a maximal family 𝒜 of subsets of [𝑛] such that 𝒜 contains only sets whose size is in 𝐾, and 𝐴 ⊈ 𝐵 for all {𝐴, 𝐵} ⊆ 𝒜, i.e. 𝒜 is an antichain. We present a general construction of such antichains for sets 𝐾 containing 2, but not 1. If 3 ∈ 𝐾 our construction asymptotically yields the smallest possible size of such a family, up to an 𝑜(𝑛²) error. We conjecture our construction to be asymptotically optimal also for 3 ∉ 𝐾, and we prove a weaker bound for the case 𝐾 = {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.
| Original language | English |
|---|---|
| Article number | P3 |
| Pages (from-to) | 1-14 |
| Journal | The Electronic Journal of Combinatorics |
| Volume | 20 |
| Issue number | 2 |
| Publication status | Published - 9 Apr 2013 |
Fingerprint
Dive into the research topics of 'Maximal antichains of minimum size'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver