Sperner定理在压缩滤子上的推广研究

Extension Research of Sperner’s Theorem on Compressed Filters

摘要: 令B_n为[n]={1,2,...,n}的所有子集按包含关系构成的偏序集。Sperner定理说明B_n中最大的Sperner集族的密度为。本文研究Sperner定理在凸集上的推广，并证明Sperner定理在压缩滤子上成立。

Abstract: Let [n]={1,2,...,n} and B_n={A,A⊆[n]}. Sperner theorem states that the density of the largest Sperner family in B_n is . Our paper focuses on the extension of Sperner theorem on convex family and proves that Sperner theorem is valid on compressed filters.

1. 引言

令 $B_n$ 为 $\left[n\right]=\left\{1,2,\cdots ,n\right\}$ 的所有子集按包含关系构成的偏序集。一个集合 $A\in B_n$ 称为Sperner集族，如果对 $\forall A,B\in A$ 有 $A\not\subset B$，且 $B\not\subset A$。Sperner的一个著名结果是 $B_n$ 中最大的Sperner集族的密度为

$\left(\begin{array}{c}n\\ \lceil \frac{n}{2}\rceil \end{array}\right)/2^n$ [1]。Sperner 定理是极值组合理论的核心结果之一，并且它有很多一般化的结果和延伸(详

见 [2] [3] )。

定义1.1 $P\in B_n$，对于 $\forall A,B\in P$，若 $A\in C\in B$ 则 $C\in P$，则称 $P$ 是凸集。

定义1.2 $I\in B_n$，对于 $\forall A\in I$，若 $B\subseteq A$ 则 $B\in I$，则称 $I$ 是理想。

很明显理想一定是凸集。由Sperner定理出发，有Frankl猜想如下，

猜想1.3 [4] 对集合 $\left[n\right]$ 上每一个凸集族 $P$，均存在一个Sperner集族 $A\subseteq P$，有

$\left|A\right|/\left|P\right|\ge \left(\begin{array}{c}n\\ \lceil \frac{n}{2}\rceil \end{array}\right)/2^n$.

这个猜想已经存在将近40年的时间了，并且到目前为止仍未被证明。很自然的人们开始考虑在理想这个特殊的凸集上猜想是否成立。牟丽丽和王毅给出 $B_n$ 中压缩理想 $I$ 的最大Sperner集族的密度至少为

$\left(\begin{array}{c}n\\ \lceil \frac{n}{2}\rceil \end{array}\right)/2^n$ [5]。Dwight Duffus等人给出 $B_n$ 中所有非空二进制理想 $D$ 的最大Sperner集族的密度至少为 $\left(\begin{array}{c}n\\ \lceil \frac{n}{2}\rceil \end{array}\right)/2^n$ [6]。

定义1.4 $\forall A\in F$，若 $A\subseteq B$，则一定有 $B\in F$，那么 $F$ 称为滤子。

因为滤子也是特殊的凸集，基于这个事实，本文考虑 $B_n$ 中压缩滤子的最大Sperner集族的密度情况。

定义1.5 序 $\underset{\_}{\prec }$ 的定义为，对 $\forall A,B\in B_n$， $A\underset{\_}{\prec }B$ 当且仅当 $A=B$ 或 $\max \left(\left(A\backslash B\right)\cup \left(B\backslash A\right)\right)\in A$。

如 $\left\{2,3,4\right\}\underset{\_}{\prec }\left\{1,2\right\}$， $\left\{2,3,4\right\}\underset{\_}{\prec }\left\{1,2,4\right\}$ ； $B_4$ 在序 $\underset{\_}{\prec }$ 下的形式如图1。

定义1.6 $\forall A^{\left(k\right)}\subseteq B_n^{\left(k\right)}$， $C\left(A^{\left(k\right)}\right)$ 是 $B_n^{\left(k\right)}$ 在序°下的前 $\left|A^{\left(k\right)}\right|$ 个元素，这里C记为压缩算子。其中 $B_n^{\left(k\right)}$ 代

表 $B_n$ 的所有k-子集构成的集合， $A^{\left(k\right)}$ 代表 $A$ 的所有k-子集构成的集合。

那么对 $\forall A\subseteq B_n$， $A={\displaystyle \underset{k\in \left[n\right]}{\cup }{A}^{\left(k\right)}}$， $C\left(A\right)={\displaystyle \underset{k\in \left[n\right]}{\cup }\left(C\left(A^{\left(k\right)}\right)\right)}$。如在 $B_4$ 中，若

$A=\{\{1,2,3,4\},\left\{2,3,4\right\},\left\{1,2,4\right\},\{1,2,3\}\}$，则 $C\left(A\right)=\left\{\left\{1,2,3,4\right\},\left\{2,3,4\right\},\left\{1,3,4\right\},\left\{1,2,4\right\}\right\}$。

Figure 1. $B_4$

图1. $B_4$

定义1.7 对滤子 $F$，若有 $C\left(F\cap B_n^{\left(k\right)}\right)=F\cap B_n^{\left(k\right)}$， $0\le k\le n$，则称 $F$ 为压缩滤子。很明显 $B_n$ 是压缩滤子。

在本文中将证明结论如下。

定理1.8 令 $F$ 为 $B_n$ 中的一个压缩滤子， $B_n$ 中存在最大Sperner集族 $A\in F$ 使

$\left|A\right|/\left|F\right|\ge \left(\begin{array}{c}n\\ \lceil \frac{n}{2}\rceil \end{array}\right)/2^n$ (1)

2. 定理证明

为了证明定理1.8，还需要知道以下定义及引理。

定义2.1 $A$ 的上阴 $\nabla A$ ： $A\subseteq B_n^{\left(k\right)}$，则 $\nabla A=\left\{B\in B_n^{\left(k+1\right)}:\exists A\in A,A\subset B\right\}$，其中 $k<n$。

定义2.2 $A$ 的下阴 $\Delta A$ ： $A\subseteq B_n^{\left(k\right)}$，则 $\Delta A=\left\{B\in B_n^{\left(k-1\right)}:\exists A\in A,B\subset A\right\}$，其中 $k<n$。

引理2.3 [2] 令 $M\subseteq B_n^{\left(k\right)}$，当 $k>\lceil \frac{n}{2}\rceil$ 时， $\left|\Delta M\right|>\left|M\right|$ ； $k<\lfloor \frac{n}{2}\rfloor$ 时， $\left|\nabla M\right|>\left|M\right|$。

引理2.4 [7] 令 $M\subseteq B_n^{\left(k\right)}$，那么存在一个 $x\ge k$ 使 $\left|M\right|=\left(\begin{array}{c}x\\ k\end{array}\right)$ 且 $\left|\Delta M\right|\ge \left(\begin{array}{c}x\\ k-1\end{array}\right)$ ；同样它的对偶情况也成立，即存在一个 $x\ge k$ 使 $\left|M\right|=\left(\begin{array}{l}x\\ k\end{array}\right)$ 且 $\left|\nabla M\right|\ge \left(\begin{array}{c}x\\ k-1\end{array}\right)$。

通常

$\left(\begin{array}{l}x\\ k\end{array}\right)=\frac{x\left(x-1\right)\cdots \left(x-k+1\right)}{k!}$

其中 $x\in {ℝ}^{+},k\in {\mathbb{Z}}^{+}$。

为了方便证明，令

$T\left(n\right)=\left(\begin{array}{c}n\\ \lceil \frac{n}{2}\rceil \end{array}\right)/2^n$

容易计算得 $T\left(2n-1\right)=T\left(2n\right);T\left(2n\right)/T\left(2n+1\right)=\left(2n+2\right)/\left(2n+1\right)$，因此有下式成立

$T\left(1\right)=T\left(2\right)>T\left(3\right)=T\left(4\right)>\cdots >T\left(2m-1\right)=T\left(2m\right)>\cdots$

用归纳假设法来证明定理1.8。

当 $n=1$ 时显然成立。假设 $n-1$ 时(1)式也成立，现来看n时的情况。令 $F$ 为 $B_n$ 中的一个压缩滤子， $F=F_1\cup F_2$， $F_1=\left\{A\in F:n\in A\right\}$， $F_2=\left\{A\in F:n\notin A\right\}$， $F_1\left(\bar{n}\right)$ 为 $A\backslash \left\{n\right\}$ 的所有集合，其中 $A\in F_1$。由定义知 $F_1\left(\bar{n}\right),F_2\in B_{n-1}$，且均为 $B_{n-1}$ 中的压缩滤子。因此由归纳假设在 $B_{n-1}$ 中，存在最大Sperner集族 $A_1\left(\bar{n}\right)\subseteq F_1\left(\bar{n}\right)$ 和 $A_2\subseteq F_2$ 有

$\frac{\left|A_1\left(\bar{n}\right)\right|}{\left|F_1\left(\bar{n}\right)\right|}\ge T\left(n-1\right),\frac{\left|A_2\right|}{\left|F_2\right|}\ge T\left(n-1\right)$ (2)

令 $A_1=\left\{A\cup \left\{n\right\}:A\in A_1\left(\bar{n}\right)\right\}$，那么 $A_1$ 为 $F_1$ 中最大反链，有

$\frac{\left|A_1\right|}{\left|F_1\right|}=\frac{\left|A_1\left(\bar{n}\right)\right|}{\left|F_1\left(\bar{n}\right)\right|}\ge T\left(n-1\right)\ge T\left(n\right)$ (3)

其中 $F_i^{\left(k\right)}$ 代表 $F_i$ 在 $B_n^{\left(k\right)}$ 中的所有元素集合， $A_i^{\left(k\right)}$ 代表 $A_i$ 在 $B_n^{\left(k\right)}$ 中的所有元素集合， $i=1,2$。取 $s=\max \left\{k:A_1^{\left(k\right)}\ne \varnothing \right\}$， $r=\min \left\{k:A_2^{\left(k\right)}\ne \varnothing \right\}$。则由压缩滤子的定义有 $F_1^{\left(r\right)}=B_{n-1}^{\left(r-1\right)}\cup \left\{n\right\}$。所以 $F_1$ 可写成如下形式：

$F_1=\left({\displaystyle \underset{k=r}{\overset{n}{\cup }}{B}_{n-1}^{\left(k-1\right)}\cup \left\{n\right\}}\right)\cup {\displaystyle \underset{k<r}{\cup }{F}_1^{\left(k\right)}}$ (4)

现来证 $r\ge \lfloor \frac{n}{2}\rfloor$。由已知 $A_2^{\left(r\right)}\subseteq B_{n-1}^{\left(r\right)}\subseteq B_n^{\left(r\right)}$，如果则 $r<\lfloor \frac{n}{2}\rfloor$ 由引理2.3有

$\left|\nabla A_2^{\left(r\right)}\right|>\left|A_2^{\left(r\right)}\right|$

用 $\nabla A_2^{\left(k\right)}$ 代替 $A_2^{\left(k\right)}$，可在 $F_2$ 中的到一个比 $A_2$ 更大的Sperner 集族，与已知矛盾，所以 $r\ge \lfloor \frac{n}{2}\rfloor$。

下面分两种情况证明 $F$ 中存在最大Sperner 集族 $A$ 使(1)成立。

情况1：n为偶数时，令 $n=2m$。则 $r\ge m$，现来证 $s\le r$。假设 $s>r$，令

$\overline{A_1}=\left(A_1\backslash \left\{A_1\cap F_1^{\left(s\right)}\right\}\right)\cup \left({\Delta }^{\left(r\right)}\left(A_1\cap F_1^{\left(s\right)}\right)\right)$

其中

${\Delta }^{\left(r\right)}\left(A_1\cap F_1^{\left(s\right)}\right)=\left\{A\in B_{2m}^r:\exists B\in A_1\cap F_1^{\left(s\right)},A\subset B\right\}$

由(4)知 ${\Delta }^{\left(r\right)}\left(A_1\cap F_1^{\left(s\right)}\right)\subset F_1$ 并且 $\overline{A_1}$ 在 $F_1$ 中仍是一个Sperner集族，由引理2.3有

$\left|{\Delta }^{\left(r\right)}\left(A_1\cap F_1^{\left(s\right)}\right)\right|>\left|A_1\cap F_1^{\left(s\right)}\right|$

即 $\left|\overline{A_1}\right|>\left|A_1\right|$，这与 $A_1$ 为 $F_1$ 中最大的Sperner 集族矛盾，所以 $s\le r$。因此 $A_1\cup A_2$ 在 $F$ 中仍是一个Sperner集族。由(2)和(3)有

$\frac{\left|A_1\cup A_2\right|}{\left|F\right|}=\frac{\left|A_1\right|+\left|A_2\right|}{\left|F_1\right|+\left|F_2\right|}\ge T\left(2m-1\right)=T(\; 2\; m\; )$

因此 $A=A_1\cup A_2$ 是 $F$ 中最大的Sperner集族。

情况2：n为奇数时，令 $n=2m-1$，则 $r\ge m-1$。如果 $r>m-1$，由(4)知与情况1类似可得到 $s\le r$，且 $A=A_1\cup A_2$ 是 $F$ 中最大的Sperner集族。如果 $r=m-1$，

$F_1=\left({\displaystyle \underset{k=r}{\overset{2m-1}{\cup }}{B}_{2m-2}^{\left(k-1\right)}\cup \left\{2m-1\right\}}\right)\cup {\displaystyle \underset{k<m-1}{\cup }{F}_1^{(\; k\; )}}$

其中 $A_1=B_{2m-2}^{\left(m-1\right)}\cup \left\{2m-1\right\}$，但这时 $\left(B_{2m-2}^{\left(m-1\right)}\cup \left\{2m-1\right\}\right)\cup A_2$ 不是一个Sperner 集族。令

$\overline{A_2}=\left(A_2\backslash \left\{A_2^{\left(m-1\right)}\right\}\right)\cup \left(\nabla \left(A_2^{\left(m-1\right)}\right)\right)$

其中 $\nabla \left(A_2^{\left(m-1\right)}\right)$ 是 $A_2^{\left(m-1\right)}$ 在 $F_2$ 中的上阴。在 $F_2$ 中 $\overline{A_2}$ 仍是一个Sperner 集族，那么 $\left(B_{2m-2}^{\left(m-1\right)}\cup \left\{2m-1\right\}\right)\cup \overline{A_2}$ 在 $F$ 中仍是一个Sperner 集族。下证

$\frac{\left|\left(B_{2m-2}^{\left(m-1\right)}\cup \left\{2m-1\right\}\right)\cup \overline{A_2}\right|}{\left|F_1\right|+\left|F_2\right|}\ge T\left(2m-1\right)$ (5)

这里 $\left|B_{2m-2}^{\left(m-1\right)}\cup \left\{2m-1\right\}\right|=\left(\begin{array}{c}2m-2\\ m-1\end{array}\right)$，即证

$\frac{\left|\left(\begin{array}{c}2m-2\\ m-1\end{array}\right)\right|+\left|\overline{A_2}\right|}{\left|F_1\right|+\left|F_2\right|}\ge \left(\begin{array}{c}2m-1\\ m\end{array}\right)/2^{2m-1}$

整理有

$2^{2m-1}\left(\begin{array}{c}2m-2\\ m-1\end{array}\right)+2^{2m-1}\left|\overline{A_2}\right|\ge \left(\begin{array}{c}2m-1\\ m\end{array}\right)\left(\left|F_1\right|+\left|F_2\right|\right)$

因为 $\text{max}\left|F_1\right|=2^{2m-2}$，所以可转化为证

$2^{2m-1}\left(\begin{array}{c}2m-2\\ m-1\end{array}\right)+2^{2m-1}\left|\overline{A_2}\right|\ge 2^{2m-2}\left(\begin{array}{c}2m-1\\ m\end{array}\right)+\left(\begin{array}{c}2m-1\\ m\end{array}\right)\left|F_2\right|$

逐步整理如下

$\begin{array}{l}\frac{2^{2m-1}}{2m}\left(\begin{array}{c}2m-2\\ m-1\end{array}\right)+2^{2m-1}\left|\overline{A_2}\right|\ge \left(\begin{array}{c}2m-1\\ m\end{array}\right)\left|F_2\right|\\ \frac{1}{2m}\left(\begin{array}{c}2m-2\\ m-1\end{array}\right)+\left|\overline{A_2}\right|\ge \frac{T\left(2m-1\right)}{T\left(2m\right)}\left|A_2\right|\\ \left(\begin{array}{c}2m-2\\ m-1\end{array}\right)\ge \left(2m-1\right)\left|A_2\right|-2m\left|\overline{A_2}\right|\end{array}$

这里由

$\begin{array}{l}\left|A_2\right|=\left|A_2^{\left(m-1\right)}\right|+{\displaystyle \underset{i>m-1}{\sum }\left|A_2^{\left(i\right)}\right|}\\ \left|\overline{A_2}\right|=\left|\nabla \left(A_2^{\left(m-1\right)}\right)\right|+{\displaystyle \underset{i>m-1}{\sum }\left|A_2^{\left(i\right)}\right|}\end{array}$

我们有

$\begin{array}{l}\left(2m-1\right)\left|A_2\right|-2m\left|\overline{A_2}\right|\\ =\left(2m-1\right)\left|A_2^{\left(m-1\right)}\right|-\left(2m-1\right)\left|A_2^{\left(m-1\right)}\right|-{\displaystyle \underset{i>m-1}{\sum }\left|A_2^{\left(i\right)}\right|}\\ \le \left(2m-1\right)\left|A_2^{\left(m-1\right)}\right|-\left(2m-1\right)\left|A_2^{\left(m-1\right)}\right|\end{array}$

因此证(5)式转化为证

$\left(\begin{array}{c}2m-2\\ m-1\end{array}\right)\ge \left(2m-1\right)\left|A_2^{\left(m-1\right)}\right|-2m\left|\nabla \left(A_2^{\left(m-1\right)}\right)\right|$ (6)

由 $A_2^{\left(m-1\right)}\subseteq F_2^{\left(m-1\right)}\subseteq B_{2m-2}^{\left(m-1\right)}$，假设

$\left|A_2^{\left(m-1\right)}\right|=\left(\begin{array}{c}x\\ m-1\end{array}\right)$

其中 $m-1\le x\le 2m-2$，那么由引理2.4有

$\left|\nabla \left(A_2^{\left(m-1\right)}\right)\right|\ge \left(\begin{array}{c}x\\ m-2\end{array}\right)$

那么

$\begin{array}{l}\left(2m-1\right)\left|A_2^{\left(m-1\right)}\right|-2m\left|\nabla \left(A_2^{\left(m-1\right)}\right)\right|\\ \le \left(2m-1\right)\left(\begin{array}{c}x\\ m-1\end{array}\right)-2m\left(\begin{array}{c}x\\ m-2\end{array}\right)\\ =\left(\left(2m-1\right)\cdot \frac{x-m+2}{m-1}-2m\right)\left(\begin{array}{c}x\\ m-2\end{array}\right)\\ \le \left(\left(2m-1\right)\cdot \frac{2m-2-m+2}{m-1}-2m\right)\left(\begin{array}{c}2m-2\\ m-2\end{array}\right)\\ =\frac{m}{m-1}\left(\begin{array}{c}2m-2\\ m-2\end{array}\right)=\left(\begin{array}{c}2m-2\\ m-1\end{array}\right)\end{array}$

由此(6)式得证，综上定理1.8证毕。 □

3. 结论

$B_n$ 中压缩滤子 $F$ 的Sperner集族的密度至少为 $\left(\begin{array}{c}n\\ \lceil \frac{n}{2}\rceil \end{array}\right)/2^n$。

参考文献