Minimising the total number of subsets and supersets

Let F be a family of subsets of a ground set {1, . . . , n} with |F| = m, and let F-up down arrow denote the family of all subsets of {1, . . . , n} that are subsets or supersets of sets in F. Here we determine the minimum value that |F-up down arrow| 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, . . . , 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, . . . , n} such that, for each initial segment F of this ordering, F-up down arrow 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. (c) 2023 The Author(s). Published by Elsevier Ltd. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

Automated summary

This article determines the minimum value of a family F, denoted as |F-up down arrow|, as a function of the size of the ground set and the family itself. It solves the isoperimetric problem on a graph and provides insights into the isoperimetric problem for hypercubes. Additionally, it has implications for the study of cross-Sperner families.