{
  "id": "2212.13112",
  "version": "v1",
  "published": "2022-12-26T12:31:06.000Z",
  "updated": "2022-12-26T12:31:06.000Z",
  "title": "Minimising the total number of subsets and supersets",
  "authors": [
    "Adam Gowty",
    "Daniel Horsley",
    "Adam Mammoliti"
  ],
  "comment": "21 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\mathcal{F}$ be a family of subsets of a ground set $\\{1,\\ldots,n\\}$ with $|\\mathcal{F}|=m$, and let $\\mathcal{F}^{\\updownarrow}$ denote the family of all subsets of $\\{1,\\ldots,n\\}$ that are subsets or supersets of sets in $\\mathcal{F}$. Here we determine the minimum value that $|\\mathcal{F}^{\\updownarrow}|$ can attain as a function of $n$ and $m$. This can be thought of as a `two-sided' Kruskal-Katona style result. It also gives a solution to the isoperimetric problem on the graph whose vertices are the subsets of $\\{1,\\ldots,n\\}$ and in which two vertices are adjacent if one is a subset of the other. This graph is a supergraph of the $n$-dimensional hypercube and we note some similarities between our results and Harper's theorem, which solves the isoperimetric problem for hypercubes. In particular, analogously to Harper's theorem, we show there is a total ordering of the subsets of $\\{1,\\ldots,n\\}$ such that, for each initial segment $\\mathcal{F}$ of this ordering, $\\mathcal{F}^{\\updownarrow}$ has the minimum possible size. Our results also answer a question that arises naturally out of work of Gerbner et al. on cross-Sperner families and allow us to strengthen one of their main results.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-12-26T12:31:06.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05",
      "05C35",
      "05C69"
    ],
    "keywords": [
      "total number",
      "harpers theorem",
      "isoperimetric problem",
      "kruskal-katona style result",
      "minimising"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}