Let $n\geqslant 4$ be a natural number, and let $K$ be a set $K\subseteq [n]:=\{1,2,\dots,n\}$. We study the problem of finding the smallest possible size of a maximal family $\mathcal{A}$ of subsets of $[n]$ such that $\mathcal{A}$ contains only sets whose size is in $K$, and $A\not\subseteq B$ for all $\{A,B\}\subseteq\mathcal{A}$, i.e. $\mathcal{A}$ is an antichain. We present a general construction of such antichains for sets $K$ containing 2, but not 1. If $3\in 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\not\in 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.
1
Universität Rostock
2
University of Wisconsin-Superior
Thomas Kalinowski; Uwe Leck; Ian T. Roberts. Maximal antichains of minimum size. The electronic journal of combinatorics, Tome 20 (2013) no. 2. doi: 10.37236/2736
@article{10_37236_2736,
author = {Thomas Kalinowski and Uwe Leck and Ian T. Roberts},
title = {Maximal antichains of minimum size},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {2},
doi = {10.37236/2736},
zbl = {1267.05281},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2736/}
}
TY - JOUR
AU - Thomas Kalinowski
AU - Uwe Leck
AU - Ian T. Roberts
TI - Maximal antichains of minimum size
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/2736/
DO - 10.37236/2736
ID - 10_37236_2736
ER -
%0 Journal Article
%A Thomas Kalinowski
%A Uwe Leck
%A Ian T. Roberts
%T Maximal antichains of minimum size
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2736/
%R 10.37236/2736
%F 10_37236_2736
