### Abstract

Original language | English |
---|---|

Pages (from-to) | P3-1-P3-14 |

Number of pages | 14 |

Journal | Electronic Journal of Combinatorics |

Volume | 20 |

Issue number | 2 |

Publication status | Published - 2013 |

### Fingerprint

### Cite this

*Electronic Journal of Combinatorics*,

*20*(2), P3-1-P3-14.

}

*Electronic Journal of Combinatorics*, vol. 20, no. 2, pp. P3-1-P3-14.

**Maximal antichains of minimum size.** / Kalinowski, Thomas; Leck, Uwe; Roberts, Ian.

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

TY - JOUR

T1 - Maximal antichains of minimum size

AU - Kalinowski, Thomas

AU - Leck, Uwe

AU - Roberts, Ian

PY - 2013

Y1 - 2013

N2 - 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 2 ) 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.

AB - 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 2 ) 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.

M3 - Article

VL - 20

SP - P3-1-P3-14

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

SN - 1077-8926

IS - 2

ER -