{
  "id": "2106.02226",
  "version": "v1",
  "published": "2021-06-04T03:03:01.000Z",
  "updated": "2021-06-04T03:03:01.000Z",
  "title": "Maximal antichains of subsets I: The shadow spectrum",
  "authors": [
    "Jerrold R. Griggs",
    "Thomas Kalinowski",
    "Uwe Leck",
    "Ian T. Roberts",
    "Michael Schmitz"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Extending a classical theorem of Sperner, we investigate the question for which positive integers $m$ there exists a maximal antichain of size $m$ in the Boolean lattice $B_n$, that is, the power set of $[n]:=\\{1,2,\\dots,n\\}$, ordered by inclusion. We characterize all such integers $m$ in the range $\\binom{n}{\\lceil n/2\\rceil}-\\lceil n/2\\rceil^2\\leq m\\leq\\binom{n}{\\lceil n/2\\rceil}$. As an important ingredient in the proof, we initiate the study of an extension of the Kruskal-Katona theorem which is of independent interest. For given positive integers $t$ and $k$, we ask which integers $s$ have the property that there exists a family $\\mathcal F$ of $k$-sets with $\\lvert\\mathcal F\\rvert=t$ such that the shadow of $\\mathcal F$ has size $s$, where the shadow of $\\mathcal F$ is the collection of $(k-1)$-sets that are contained in at least one member of $\\mathcal F$. We provide a complete answer for the case $t\\leq k+1$. Moreover, we prove that the largest integer which is not the shadow size of any family of $k$-sets is $\\sqrt 2k^{3/2}+\\sqrt[4]{8}k^{5/4}+O(k)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-06-04T03:03:01.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "06A07",
      "05D05"
    ],
    "keywords": [
      "maximal antichain",
      "shadow spectrum",
      "positive integers",
      "boolean lattice",
      "power set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}