极值集合

1 太阳花

集合系统(集族)$\mathcal F\in 2^{[n]}$, ground set $[n]$

sunflowers:
$\mathcal F$是一个以$C$为中心的大小为$r$的太阳花, 即 $|\mathcal F|=r$, $\forall S,T\in \mathcal F, S\cap T=C$.

太阳花引理(Erdős-Rado):

如果$\mathcal F\subseteq \binom{X}{k}$, $|\mathcal F|>k!(r-1)^k$, 则存在太阳花$\mathcal G\subseteq \mathcal F$, $|\mathcal G|=r$.

证明(对$k$归纳):

当$k=1$时, $\mathcal F\subseteq \binom{X}{1}$, 所以$\mathcal F$中每个集合都是不相交的. 因为$|\mathcal F|> r-1$, 所以任意选$r$个集合就可以形成一个太阳花.
$k\ge 2$时, 取最大的不相交的$\mathcal G\subseteq \mathcal F$, 即
- case 1: $|\mathcal G| \ge r$, $\mathcal G$是大小为$r$的太阳花
- case 2: $|G|\le r-1$, 目标: 找一个足够popular的$x\in X$, 使足够多的集合都包含$x$
  - 令$Y=\cup_{S\in \mathcal G} S$. 则$|Y|=k|\mathcal G|\le k(r-1)$
  - $Y$一定和所有$S\in \mathcal G$相交, 否则和最大矛盾.
  - 根据鸽笼原理, 一定存在$y\in Y$至少被 $\frac{|\mathcal F|}{|Y|}>\frac{k!(r-1)^k}{k(r-1)}=(k-1)!(r-1)^{k-1}$ 个$\mathcal F$中集合包含.
  - 我们从这些集合中删除$y$, 则考虑集族$\mathcal H=\{S\setminus\{y\}|S\in \mathcal F \land y\in S\}$.
  - 有$\mathcal H\subseteq \binom{X}{k-1}$, 因为$|\mathcal H|>(k-1)!(r-1)^{k-1}$, 根据归纳法, $\mathcal H$中有大小为$r$的太阳花.
  - 把$y$加入这些太阳花, 就得到了原集族$\mathcal F$的太阳花
得证.

2 The Erdős–Ko–Rado Theorem

一个集族$\mathcal F\subseteq 2^X$, 如果对于任意$S,T\in \mathcal F$, $S\cap T\ne \emptyset$, 则称为相交的.

Erdős–Ko–Rado theorem (proved in 1938, published in 1961):

令$\mathcal F\subseteq \binom{X}{k}$, 其中$|X|=n$且$n\ge 2k$. 如果$\mathcal F$是相交的, 那么

$|\mathcal F|\le \binom{n-1}{k-1}$

2.1 Katona’s proof

令$\pi$是$X$的一个环排列, 则$n$元集上有$(n-1)!$个环排列(忽略旋转). 令

$\mathcal G_{\pi}=\{\{\pi_{i+j\mod n}|j\in [k]\}|i\in[n]\}$

下面的引理说明, 在$n$点的环上, 假设$n\ge 2k$, 至多有$k$段弧, 每段有$k$个点, 每一对弧至少共享一个点.

引理: 令$\mathcal F\subseteq \binom{X}{k}$, $|X|=n$, $n\ge 2k$. 如果$\mathcal F$是相交的, 那么对于任意$X$的环排列$\pi$, 有$|\mathcal G_\pi\cap \mathcal F|\le k$.

证明: 固定$X$的环排列$\pi$, 令$A_i=\{\pi_{(i+j+n)\mod n}|j\in [k]\}$, 那么$\mathcal G_\pi$可以写成$\mathcal G_\pi=\{A_i|i\in[n]\}$.

假设$A_t\in \mathcal F$. 因为$\mathcal F$是相交的, 如果除$A_t$以外的$A_i\in \mathcal F$, 则$t-(k-1)\le i\le t+k-1, i\ne t$, 有$2k-2$个这样的集合. 我们把它们分成$k-1$对$\{A_i,A_{i+k}\}$, $t-(k-1)\le i\le t-1$.

因为$n\ge 2k$, 所以$A_i\cap A_{i+k}=\emptyset$, 所以这$k-1$对中, 每一对至多有一个在$\mathcal F$中. 得证.

Katona’s proof of Erdős–Ko–Rado theorem:(double counting)

令$\mathcal R=\{(S,\pi)|\pi\text{ is a cyclic permutation of }X, \text{ and }S\in\mathcal F\cap G_\pi\}$. 下面用两种方法数$|\mathcal R|$:

根据引理, $|\mathcal R|=\sum_{\text{cyclic }\pi}|\mathcal F\cap G_\pi|\le k(n-1)!$
对于每个$S\in\mathcal F$, 让$S$中元素连续的排列$\pi$的数量为$|S|!(n-|S|)!$, 所以
$|\mathcal R|=\sum_{S\in \mathcal F}k!(n-k)!=|\mathcal F|k!(n-k)!$

因此有

$|\mathcal F|\le \frac{k(n-1)!}{k!(n-k)!}=\binom{n-1}{k-1}$

2.2 Erdős’ shifting technique

不失一般性, 设$X=[n]$, 则Erdős–Ko–Rado theorem定理如下:
令$\mathcal F\subseteq \binom{[n]}{k}$, 其中$n\ge 2k$. 如果$\mathcal F$是相交的, 那么

$|\mathcal F|\le \binom{n-1}{k-1}$

定义shift操作:
假设$\mathcal F\subseteq 2^{[n]}$, 且$0\le i<j\le n-1$. 定义$(i,j)-$shift $S_{ij}$为$\mathcal F$上的操作符, 定义如下:

对于任意$T\in\mathcal F$, $T_{ij}=(T\setminus \{j\})\cup \{i\}$. 令 $S_{ij}=\begin{cases} T_{ij}&\text{if }j\in T,i\not\in T, \text{and }T_{ij}\not\in T,\\ T&\text{otherwise;} \end{cases}$
$S_{ij}(\mathcal F)=\{S_{ij}(T)|T\in\mathcal F\}$

则有如下性质:

$|S_{ij}(T)|=|T|$且$|S_{ij}(\mathcal F)|=|\mathcal F|$
如果$\mathcal F$是相交的, 那么$S_{ij}(\mathcal F)$也是相交的
- 唯一的坏情况是$A,B\in\mathcal F$, $A\cap B=\{j\}$, $A_{ij}\in\mathcal F$, $B_{ij}\not\in\mathcal F$, 则$A_{ij}\cap B=\emptyset$, 矛盾.

定义shifted:
对于$1\le i<j\le n$重复执行$S_{ij}(\mathcal F)$, 直到$\mathcal F$不被任何$S_{ij}(\mathcal F)$改变, 则称为$\mathcal F$是shifted.

Erdős-Ko-Rado’s证明:
只要证明shifted $\mathcal F’$满足$|\mathcal F’|\le \binom{n-1}{k-1}$, 就说明$|\mathcal F|\le \binom{n-1}{k-1}$. 所以不妨设$\mathcal F$是shifted.

$k=1$成立.
当$n=2k$时, $\forall S\in\binom{[n]}{k}$, $S$和$\overline S$中至多一个在$\mathcal F$中. 所以$|\mathcal F|\le \frac{1}{2}\binom{n}{k}=\binom{n-1}{k-1}$.
当$n>2k$时: 注意$\mathcal F$是shifted的!
- $\mathcal F_1=\{S\in F|n\in S\}$, $\mathcal F_1’=\{S\setminus\{n\}|S\in F_1\}$, 则$\mathcal F_1’$是相交的, 根据假设$|\mathcal F_1’|\le \binom{n-2}{k-2}$.
  - 反证: 如果存在$A,B\in\mathcal F$, $A\cap B=\{n\}$, $|A\cup B|\le 2k-1<n-1$, 所以存在$i<n$, $i\not\in A\cup B$. 因为$\mathcal F$是shifted的, 所以 $C=A\setminus\{n\}\cup\{i\}\in\mathcal F$, 所以$C\cap B=\emptyset$
- $F_0=\{S\in \mathcal F|n\not\in S\}$是相交的, 根据假设$|\mathcal F_0|\le \binom{n-2}{k-1}$.
- $|\mathcal F|=|\mathcal F_0|+|\mathcal F_1|=|\mathcal F_0|+|\mathcal F_1’|\le \binom{n-2}{k-1}+\binom{n-2}{k-2}=\binom{n-1}{k-1}$.
证毕.

3 Sperner system

定义反链: 对于集族$\mathcal F\subseteq 2^X$, 如果任意$S,T\subseteq \mathcal F$, $S\ne T$, 有$S\not\subseteq T$, 则$\mathcal F$是反链.

Theorem (Sperner 1928):

令$\mathcal F\subseteq 2^X$, $|X|=n$. 如果$\mathcal F$是反链, 则

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

3.1 证明1(shadow)

定义: $|X|=n$, $\mathcal F\subseteq \binom{X}{k}$, $k<n$.

shade: $\nabla F=\{T\in \binom{X}{k+1}|\exists S\in \mathcal F, S\subset T\}$

shadow: $\Delta F=\{T\in \binom{X}{k-1}|\exists S\in \mathcal F, T\subset S\}$

Lemma (Sperner):

$\mathcal F\subseteq \binom{[n]}{k}$. 则

$|\nabla F|\ge \frac{n-k}{k+1}|F|, \text{if }k<n$ $|\Delta F|\le \frac{k}{n-k+1}|F|, \text{if }k>0$

证明(double counting):

第一个不等式:

定义

$\mathcal R=\{(S,T)|S\in\mathcal F, T\in \nabla \mathcal F, S\subset T\}$

用两种方式计算$|\mathcal R|$:

对于每个$S\in\mathcal F$, 有$n-k$个不同的$T\in \nabla\mathcal F$满足$S\subset T$, 所以$|\mathcal R|=(n-k)|\nabla\mathcal F|$
对于每个$T\in\nabla \mathcal F$, 有$k+1$个不同的方法选择$S\subset T$满足$|S|=k$(未必都在$\mathcal F$中), 所以
$|\mathcal R|\le (k+1)|\nabla\mathcal F|$

因此$|\nabla\mathcal F|\ge \frac{n-k}{k+1}|\mathcal F|$.

第二个不等式同理.

因此非常容易得到下面的命题:

Proposition 1:

如果$k\le \frac{n-1}{2}$, 则$|\nabla \mathcal F|\ge |\mathcal F|$;

如果$k\ge \frac{n-1}{2}$, 则$|\Delta \mathcal F|\ge |\mathcal F|$.

Sperner定理证明思路:

将大小$<\frac{n-1}{2}$的集合$\mathcal F$用他们的shades替代;
将大小$\ge\frac{n+1}{2}$的集合$\mathcal F$用他们的shadows替代;

不断重复这个过程, 最终会得到一个集族$\mathcal F\subseteq \binom{X}{\lfloor n/2\rfloor}$. 接下来说明这个过程不会使$|\mathcal F|$减小.

Proposition 2:

假设$\mathcal F\subseteq 2^X$, $|X|=n$. 令$\mathcal F_k=\mathcal F\cap \binom{X}{k}$. 令$k_{min}$为最小的满足$|\mathcal F_k|>0$的$k$. 令

$\mathcal F'=\begin{cases} \mathcal F\setminus \mathcal F_{k_{min}}\cup \nabla \mathcal F_{k_{min}} &\text{if }k_{min}<\frac{n-1}{2}\\ \mathcal F & \text{otherwise.} \end{cases}$

类似的, 令$k_{max}$表示最大的满足$|\mathcal F_k|>0$的$k$, 令

$\mathcal F''=\begin{cases} \mathcal F\setminus \mathcal F_{k_{max}}\cup \Delta \mathcal F_{k_{max}} &\text{if }k_{max}\ge\frac{n+1}{2}\\ \mathcal F & \text{otherwise.} \end{cases}$

如果$\mathcal F$是反链, 则$\mathcal F’$和$\mathcal F’’$也是反链, 且$|\mathcal F’|\ge |\mathcal F|$, $|\mathcal F’’|\ge |\mathcal F|$.

证明过程见讲义.

根据上面命题, 很容易证明Sperner定理. 具体见讲义.

3.2 证明2(counting)

令$\pi$是$X$的排列. 如果$S=\{\pi_1,\pi_2\cdots,\pi_{|S|}\}$, 则称$S\subseteq X$是$\pi$的前缀.
固定一个$S\subseteq X$. 满足$S$ 是$\pi$的前缀的排列$\pi$有$|S|!(n-|S|)!$个. 又因为$\mathcal F$是反链, 所以没有$X$的排列$\pi$满足多个$\mathcal F$中的元素都是$\pi$的前缀. 因此满足存在$S\in\mathcal F$是$\pi$的前缀的$\pi$的数量为

$\sum_{S\in\mathcal F}|S|!(n-|S|)!$

而这个数量肯定小于$X$的排列的总数$n!$, 所以

$\sum_{S\in\mathcal F}|S|!(n-|S|)!\le n!$

即

$\sum_{S\in\mathcal F}\frac{1}{\binom{n}{|S|}}=\sum_{S\in\mathcal F}\frac{|S|!(n-|S|)!}{n!}\le 1$

又因为$\binom{n}{|S|}\le \binom{n}{\lfloor n/2\rfloor}$, 所以

$\frac{|\mathcal F|}{\binom{n}{\lfloor n/2\rfloor}}\le \sum_{S\in\mathcal F}\frac{1}{\binom{n}{|S|}}\le 1$

得证.

3.3 LYM不等式

LYM不等式:

令$\mathcal F\subseteq 2^X$, $|X|=n$. 如果$\mathcal F$是反链, 则

$\sum_{S\in\mathcal F}\frac{1}{\binom{n}{|S|}}\le 1$

第三种证明(概率法):

$\pi$是$X$的均匀随机排列. 定义一个随机的最大链为$\mathcal C_\pi=\{\{\pi_i|1\le i\le k\}|0\le k\le n\}$(建议看slides上的图).

对于任意$S\in \mathcal F$, 令$X_s$为01随机变量指示是否$S\in\mathcal C_\pi$. 因为$C_\pi$中只有一个$|S|$大小的集合, 是$\binom{X}{|S|}$上的均匀分布. 所以

$\mathbb E[X_S]=\Pr[S\in \mathcal C_\pi ]=\frac{1}{\binom{n}{|S|}}$

令$X=\sum_{S\in\mathcal F}X_s$. 则$X=|\mathcal F\cap \mathcal C_\pi|$.

$\mathbb E[X]=\sum_{S\in\mathcal F}\frac{1}{\binom{n}{|S|}}$

又因为$\mathcal F$是反链, 所以不可能和一个链有多于一个交点, 也就是$X\le 1$. 因此$\mathbb E[X]\le 1$, 得证.

4 Sauer’s lemma and VC-dimension

4.1 Shattering and the VC-dimension

shatter定义:
$\mathcal F\subseteq 2^X$为集族, 令$R\subseteq X$为一个子集. $\mathcal F$在$R$上的trace$\mathcal F|_R$定义为

$\mathcal F|_R=\{S\cap R|S\in \mathcal F\}$

如果$\mathcal F|_R=2^R$, 我们称$\mathcal F$ shatters(打碎) $R$, 即对于任意$T\subseteq R$, 存在$S\in\mathcal F$满足$T=S\cap R$.

VC-dimension定义:

集族$\mathcal F\subseteq 2^X$的VC维$VC-dim(\mathcal F)$是最大的满足$\mathcal F$ shatters $R$的$R\subseteq X$的大小.

4.2 Sauer’s Lemma

Sauer’s Lemma (Sauer; Shelah-Perles; Vapnik-Chervonenkis):

令$\mathcal F\subseteq 2^X$, $|X|=n$.如果$|\mathcal F\ge \sum_{1\le i<k}\binom{n}{i}$, 则存在$R\in\binom{X}{k}$满足$\mathcal F$shatters $R$.

即$VC-dim(\mathcal F)\ge k$.

4.3 Hereditary family

定义 hereditary family:

一个集族$\mathcal F\subseteq 2^X$是遗传(hereditary)的(也称为an ideal or an abstract simplicial complex), 如果

$S\subseteq T\in\mathcal F\text{ implies } S\in\mathcal F$

命题: 令$\mathcal F$为一个遗传集族. 如果$R\in \mathcal F$, 则$\mathcal F$ shatters $R$.

引理: 对于$\mathcal F\subseteq 2^X$, $|X|=n$. 如果$\mathcal F$是遗传的, 且$|\mathcal F|>\sum_{1\le i<k}\binom{n}{i}$, 则存在$R\in\binom{X}{k}$满足$\mathcal F$ shatters $R$

证明: 因为$\mathcal F$是遗传的, 所以我们只需要证明存在$R\in\mathcal F$且$|R|\ge k$. 假设$\mathcal F$的元素大小都$<k$, 则

$|\mathcal F|\le |\cup _{1\le i<k}\binom{X}{k}|=\sum_{1\le i<k}\binom{n}{i}$

推出矛盾.

4.4 Down-shifts

定义 (down-shifts):

假设$\mathcal F\subseteq 2^{[n]}$, $i\in[n]$. 定义down-shift操作符如下:

对于任意$T\in\mathcal F$, 令
$S_i(T)=\begin{cases} T\setminus \{i\} & \text{if }i\in T\text{ and }T\setminus\{i\}\not \in\mathcal F\\ T &\text{otherwise.} \end{cases}$
令$S_i(\mathcal F)=\{S_i(T)|T\in\mathcal F\}$

对于所有的$i\in[n]$, 对$\mathcal F$使用$S_i$, 直到$\mathcal F$不再被任何$S_i$改变, 称为down-shifted.

定理: 如果$\mathcal F\subseteq 2^X$是down-shifted, 则$ \mathcal F$是遗传的.

命题:

$|S_i(\mathcal F)|=|\mathcal F|$
$|S_i(\mathcal F)|_R|=|\mathcal F|_R|$, 所以如果$S_i(\mathcal F)$ shatters $R$, $\mathcal F$也是.

由上面命题易证Sauer’s lemma.