Sperner 定理及其推广

· · 算法·理论

定义

定义 [n] 为 \{1,2,\cdots,n\}。

定义 \mathcal P(S) 为 S 的所有子集关于包含关系形成的偏序集。

对于集合 S，定义 \dbinom{S}{k} 为 S 的所有 k 元子集组成的集合。

定理内容

设 \mathcal F 为 \mathcal P([n]) 的一个反链，则

|\mathcal F|\le\binom{n}{\lfloor\frac n 2\rfloor}

等号在 \mathcal F=\dbinom{[n]}{\lfloor\frac n 2\rfloor} 或 \mathcal F=\dbinom{[n]}{\lceil\frac n 2\rceil} 时取到。

证明

取等条件显然，下面证明不等式。

证法 1

证法 1 里的“链”都指长度为 n+1 的链。

对于 $S\subseteq[n]$，定义 $f(S)$ 为包含 $S$ 的链的集合。设 $|S|=k$，不难证明 $|f(S)|=k!(n-k)!$，所以对于任意 $S$ 有 $|f(S)|\ge\lfloor\frac n 2\rfloor!\lceil\frac n 2\rceil!$。 因为 $\mathcal F$ 中元素没有包含关系，所以它们的 $f(S)$ 两两不交，所以 $$\sum_{S\in\mathcal F}|f(S)|\le n!$$ 又因为 $$|f(S)|\ge\lfloor\frac n 2\rfloor!\lceil\frac n 2\rceil!$$ 所以 $$|\mathcal F|\le\frac{n!}{\lfloor\frac n 2\rfloor!\lceil\frac n 2\rceil!}=\binom{n}{\lfloor\frac n 2\rfloor}$$ 得证。 #### 证法 2 考虑计算 $|\mathcal F|$ 的最大值。 设 $\mathcal F$ 中集合大小的最小值为 $k$。若 $k<\dfrac n 2$，我们在 $\dbinom{[n]}{k}$ 和 $\dbinom{[n]}{k+1}$ 中有包含关系的集合间连边，得到一个双正则二部图，左部点的度数为 $n-k$，右部点的度数为 $k+1$。对于左部点集的子集 $S$ 和它的邻域 $N(S)$，因为与 $S$ 相邻的边是与 $N(S)$ 相邻的边的子集，所以我们有 $$(n-k)|S|\le(k+1)|N(S)|$$ 由 $k<\dfrac n 2$ 可推出 $$|S|\le|N(S)|$$ 记 $S$ 为 $\mathcal F$ 中集合大小为 $k$ 的元素组成的集合，考虑在 $\mathcal F$ 中删去 $S$ 并加入 $N(S)$ 得到 $\mathcal F'$，容易验证 $\mathcal F'$ 也是反链，并且 $|\mathcal F'|\ge|\mathcal F|$。 这样，我们可以不断调整 $\mathcal F$ 直到里面所有集合大小都 $\ge\frac n 2$。类似地，我们也可以不断缩小 $\mathcal F$ 中集合大小的最大值。于是我们证明了 $|\mathcal F|$ 的最大值在 $\mathcal F$ 中集合大小均为 $\lfloor\frac n 2\rfloor$ 或集合大小均为 $\lceil\frac n 2\rceil$ 时取到。得证。 #### 证法 3 考虑 Dilworth 定理，我们尝试找出一个大小为 $\dbinom{n}{\lfloor\frac n 2\rfloor}$ 的链覆盖。 定义一条链为对称链当且仅当存在整数 $s$ 满足链中集合的大小依次为 $s,s+1,s+2,\cdots,n-s$。我们考虑证明 $\mathcal P([n])$ 可以被划分成若干不交的对称链。若可以，容易证明对称链和 $\dbinom{[n]}{\lfloor\frac n 2\rfloor}$ 中的元素双射，即这个划分就是一个大小为 $\dbinom{n}{\lfloor\frac n 2\rfloor}$ 的链覆盖。 考虑归纳证明，$n=1$ 时显然成立。设 $n=k-1$ 时成立。对于 $n=k-1$ 的对称链划分中的每条链，设它的元素依次为 $$S_1,S_2,\cdots,S_m$$ 我们将它拆成两条链 $$S_1,S_2,\cdots,S_m,S_m\cup\{k\}$$ $$S_1\cup\{k\},S_2\cup\{k\},\cdots,S_{m-1}\cup\{k\}$$ （当 $m=1$ 时忽略第二条链） 容易验证将所有链按上面方法拆分后得到的就是 $n=k$ 时的一个对称链划分。于是得证。 ### 一种推广 考虑 $n$ 维空间中的点 $(x_1,x_2,\cdots,x_n)$，其中 $x_i$ 是整数且 $0\le x_i\le p_i$，定义这些点上的偏序关系 $\preceq$：$A\preceq B$ 当且仅当对于每一维，$A$ 的坐标都小于等于 $B$ 的坐标。这个偏序集的最长反链之一为所有满足 $$\sum_{i=1}^nx_i=\left\lfloor\frac{\sum_{i=1}^np_i}2\right\rfloor$$ 的点组成的集合。 证明考虑推广证法 3，按维数归纳，用类似的方法拆分 $n-1$ 维时的链即可。 ### 参考资料 <https://zhuanlan.zhihu.com/p/581314631> <https://www.luogu.com/article/j989a4hs> <https://wuli.wiki/online/SpeThm.html>