Minimising the total number of subsets and supersets

Abstract

Let $\mathcal{F}$ be a family of subsets of a ground set $\{1,\dots ,n\}$ with $|\mathcal{F}|=m$, and let ${\mathcal{F}}^{\updownarrow }$ denote the family of all subsets of $\{1,\dots ,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,\dots ,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,\dots ,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.

arXiv comment21 pages, 1 figure

References in corpus (2)

• Shadows and intersections: stability and new proofs
• Uniqueness in Harper's vertex-isoperimetric theorem