论文标题
最小化子集和超集的总数
Minimising the total number of subsets and supersets
论文作者
论文摘要
令$ \ Mathcal {f} $为地面集的子集$ \ {1，\ ldots，n \} $，带有$ | \ Mathcal {f} | = m $，让$ \ mathcal {f}^f}^{f}^{\ Updownarrow} $表示$ \ ld of $ sept $ n e \ ld e \ ld。 $ \ Mathcal {f} $中的集合超集。在这里，我们确定$ | \ Mathcal {f}^{\ Updownarrow} | $可以作为$ N $和$ M $的函数实现的最低值。可以将其视为“双面” Kruskal-Katona风格的结果。它还可以解决图表上的等值问题的解决方案，其顶点是$ \ {1，\ ldots，n \} $的子集，如果一个是另一个子集，则两个顶点相邻。该图是$ n $维超同行的超图，我们注意到结果与Harper's定理之间的一些相似之处，该定理解决了Hyperipubes的等等问题。特别是，与Harper的定理类似，我们表明，总订购了$ \ {1，\ ldots，n \} $的子集，因此，对于本订单的每个初始段$ \ Mathcal {f} $我们的结果还回答了一个自然出于Gerbner等人的工作而出现的问题。在跨养老者的家庭中，让我们能够加强其主要结果之一。
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.
