用户: 迷亭/Sperner

我来偷偷写文章, 以记录对 Peter Frankl 和 Norihide Tokushige 的 Invitation to intersection problems for finite sets 这篇文章的阅读.

本文存在一些野蛮记号, 如下:

定理 0.1 (Sperner). 给定 $A \subset 2^{[n]}$ , 若 $\forall A, A^{'} \in A, A \neq \subset A^{'}$ . 那有 $∣ A ∣ \leq (⌊ n /2 ⌋ n)$ .

这个定理就是在说, 对于一个 $[n]$ 的幂集的子集, 如果它是反链 (元素两两不存在子集关系), 那么这个子集最大如此.

Frankl 没有给出证明. 这个定理有多种证明方法, 多是用 LYM 不等式. 但我不会 LYM 不等式, 所以以下是一个绕过 LYM 不等式的证明.

先思考一下如何构造反链, 一个简单的办法是我们规定 $A$ 的元素的基数都一样大, 那么它一定是反链. 然后注意到二项式定理, 我们知道最中间那一 (两) 项系数最大. ☝🤓诶! 这就刚好是 $(⌊ n /2 ⌋ n)$ .

主要问题就是证明这个办法构造的是最大的. 因为反链未必元素基数一样大, 例如 ${{1, 2}, {2, 3, 4}}$ 也是一个反链. 为此, 我们使用对称链分解.

定义 0.2 (对称). 链 $C \in 2^{[n]}$ 对称的, 当:

$\exists k \in [0, \frac{n}{2}] \cap N$ , $C$ 内集合基数为 $k, k + 1, k + 2, ..., n - k$ .

例 0.3. 链 ${{2}, {2, 3}, {2, 3, 5}, {2, 3, 4, 5}}$ 在 $2^{[5]}$ 对称.

例 0.4. 例 0.3 中的链不在 $2^{[6]}$ 对称.

引理 0.5. $A, B \in 2^{[n]},$ $A$ 是链, $B$ 是反链. $⟹ ∣ A \cap B ∣ \leq 1.$

证明. 反证法. 假设

\exists A, B \in A \cap B, A \neq = B

. 因为

A

是链, 那么必须

A \subset B

或者

B \subset A

. 但是又因为

B

是反链,

A

和

B

同时不能存在子集关系, 这是荒谬的. ☇

$□$

定义 0.6 (对称链分解). $i = 1 ⋃ n S_{i}$ 是偏序集 $X$ 的对称链分解, 当:

•	$i = 1 ⋃ n S_{i} = X$ .
•	$\forall i \in [1, n], S_{i}$ 是对称链.

引理 0.7. $\forall n \geq 1, 2^{[n]}$ 有对称链分解.

证明. 使用归纳法.

考虑基础情况 $n = 1$ , $2^{[1]} = {\emptyset, {1}}$ . 其本身就是一个对称链, 所以 $2^{[1]}$ 有对称链分解. 这是符合的.

再考虑归纳步骤, 归纳假设告诉我们对于 $n \geq 2$ , $2^{[n - 1]}$ 存在一个对称链分解, 不妨记它具有 $N$ 个部分, $2^{[n - 1]} = i = 1 ⋃ N C_{i} .$

现在把每个部分展开来写. 为此, 我们定义 $\forall m \in [N], k_{m} := min {∣ A ∣ : A \in C_{m}} .$

因为

C_{m}

是对称链, 所以我们便可以表示每个部分

C_{m} = {X_{m}^{i} : k_{m} \leq i \leq n - 1 - k_{m}}

. 其中

X_{m}^{k_{m}} \subset X_{m}^{k_{m} + 1} \subset ... \subset X_{m}^{n - 1 - k_{m}} .

且有

∣ X_{m}^{i} ∣ = i .

对于

1 \leq m \leq N

, 注意到可以构造:

C_{m}^{'} := {X_{m}^{k_{m}}, X_{m}^{k_{m} + 1}, ..., X_{m}^{n - 1 - k_{m}}, X_{m}^{n - 1 - k_{m}} \cup {n}},

C_{m}^{''} := {X_{m}^{k_{m}} \cup {n}, X_{m}^{k_{m} + 1} \cup {n}, ..., X_{m}^{n - 2 - k_{m}} \cup {n}} .

那么

(...)

$□$

推论 0.8. 且只有 $(⌊ n /2 ⌋ [ n ])$ 和 $(⌈ n /2 ⌉ [ n ])$ 能达到这个上界.

(...)