{
  "id": "1206.3007",
  "version": "v3",
  "published": "2012-06-14T05:13:34.000Z",
  "updated": "2013-03-09T18:12:55.000Z",
  "title": "Maximal antichains of minimum size",
  "authors": [
    "Thomas Kalinowski",
    "Uwe Leck",
    "Ian T. Roberts"
  ],
  "comment": "fixed faulty argument in Section 2, added references",
  "journal": "The Electronic Journal of Combinatorics 20(1) (2013) #P3",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $n\\geqslant 4$ be a natural number, and let $K$ be a set $K\\subseteq [n]:={1,2,...,n}$. We study the problem to find 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.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2013-03-09T18:12:55.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05"
    ],
    "keywords": [
      "maximal antichains",
      "minimum size",
      "graph removal lemma",
      "extremal graph theory",
      "weaker bound"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1206.3007K"
    }
  }
}