绍尔-谢拉赫引理

<image>

组合数学和极值集合论中，绍尔-谢拉赫引理（Sauer–Shelah lemma）断言，若集合族的VC维低，则该族不能有太多个集合。引理得名于诺贝特·绍尔和萨哈龙·谢拉赫，两人分别独立于1972年发表此结果。多个来源断言此处（以及与下文VC二氏的发现）的独立性，如。较之略早，在1971年，弗拉基米尔·瓦普尼克和亚历克塞·泽范兰杰斯合著的论文已有此结果（“VC维”即以两人为名）。谢拉赫发表引理时，亦归功于米哈·佩尔莱斯，故引理又称为佩尔莱斯-绍尔-谢拉赫引理。

布萨格洛等人称其为“关于VC维的最根本结论之一”。引理在若干方面有应用，就各发现者的研究动机而言，绍尔是研究集族的组合学，谢拉赫研究模型论，VC二氏则研究统计学。后来，引理亦用于离散几何和图论。

## 定义及叙述

设$\textstyle \mathcal{F}=\{S_1,S_2,\dots\}$为一族集合，$T$为另一集，此时所谓$T$为$\mathcal{F}$的碎裂集，意思是$T$的每个子集（包括空集和$T$本身），皆可表示成$T$与该族某集之交$T\cap S_i$。$\mathcal{F}$的VC维是其打碎的最大集的大小。

利用以上术语，绍尔-谢拉赫引理可以写成：

若$\mathcal{F}$是一族集合，且各集合中，合共只有$n$个不同元素，但$\textstyle |\mathcal{F}| > \sum_{i=0}^{k-1} {\binom{n}{i}}$，则$\mathcal{F}$打碎某个$k$元集合。

所以，若$\mathcal{F}$的VC维为$k$（故不打碎任何$k + 1$元集），则$\mathcal{F}$中至多只有$\textstyle \sum_{i=0}^{k} {\binom{n}{i}} =O(n^k)$个集合。

引理所给的界已是最优：考虑$n$元集$\{1,2,\dots, n\}$中，所有小于$k$个元素的子集，所成的族$\mathcal{F}$。该族的大小恰为$\textstyle \sum_{i=0}^{k-1} {\binom{n}{i}}$，但是不打碎任何$k$元集。

## 打碎多少集合

帕约尔将绍尔-谢拉赫引理加强为：Sous-espaces $l^n_1$ des espaces de Banach 由引述。

有限族$\mathcal{F}$必打碎至少$|\mathcal{F}|$个集合。

绍尔-谢拉赫引理为其直接推论，因为$n$元全集的子集中，只有$\textstyle \sum_{i=0}^{k-1} {\binom{n}{i}}$个的元素个数小于$k$。故$\textstyle |\mathcal{F}|>\sum_{i=0}^{k-1} {\binom{n}{i}}$时，即使全部小集皆已打碎，仍不足$|\mathcal{F}|$个，故必有打碎某个不少于$k$元的集合。

亦可将“碎裂”的概念加以限缩，变成“顺序碎裂”（order-shattered）。此时，任意集族顺序打碎的集合数，必恰好等于该族的大小。

## 证

绍尔-谢拉赫引理的帕约尔变式可使用数学归纳法证明，此证法一说出自诺加·阿隆，一说出自朗·阿哈罗尼及朗·霍尔兹曼（Ron Holzman）。

作为归纳法的起始步骤，单一个集合组成的族$\mathcal F$，能打碎空集，已足$|\mathcal F|$个。

至于递推步骤，可假设引理对任意少于$|\mathcal F|$个集合组成的族皆成立，且族$\mathcal{F}$有至少两个集合，故可选取元素$x$为其一的元素，但不属于另一集。如此便可将$\mathcal{F}$的集合分成两类：包含$x$的集合归入子族$\mathcal F_1$，不含$x$的则归入$\mathcal F_0$。

由归纳假设，两子族各自打碎的集合数，其和至少为$|\mathcal F_0| + |\mathcal F_1| = |\mathcal{F}|$。

该些碎裂集不能有元素$x$，因为若要打碎某个有$x$的集合$A$，则族中需要有含$x$的集合，也需要有不含$x$的集合，才能使该族各集与$A$的交集出齐$A$的全体子集。

若集$S$只被一个子族打碎，则数算两子族打碎的集合时，$S$计为一个，数$\mathcal{F}$打碎的集合时亦计为一个。但$S$也可能同时被两子族打碎，如此，数算两子族打碎的集合时，会将$S$计两次；不过$\mathcal F$既打碎$S$，也打碎$S\cup\{x\}$，所以$S$（和$S\cup\{x\}$）在数$\mathcal{F}$打碎的集合时，也计为两次。由此，$\mathcal F$打碎的集合数，不小于两子族各自打碎集合数之和，从而不小于$|\mathcal{F}|$。

绍尔-谢拉赫引理的原始形式还有另一种证明，利用线性代数及容斥原理，该证法由弗龙克尔·彼得和保奇·亚诺什给出。

## 应用

VC二氏原先将引理应用于证明，若考虑一族VC维固定的事件，则只需有限多个取样点，即可近似任意的概率分布（使取样所得的事件概率近似该分布下的事件概率），且取样点的个数只取决于VC维数。具体而言，有两种意义下的近似，各由参数$\varepsilon$定义：

- 取样集$S$上的概率分布定义为原分布的“$\varepsilon$近似”（$\varepsilon$-approximation），意思是每个事件被$S$以该分布取样的概率，与原概率所差不过$\varepsilon$。
- 取样集$S$（不设权重）定义为“ε网 (计算几何)”，意思是概率不小于$\varepsilon$的任一事件中，必含$S$中至少一点。

由定义，$\varepsilon$近似必为$\varepsilon$网，反之则不一定。

VC二氏以此引理证明，若某集族的VC维为$d$，则必有大小不过$O(\tfrac{d}{\varepsilon^2}\log\tfrac{d}{\varepsilon})$的$\varepsilon$近似。其后，和等发表了类似的结果，证明必存在大小为$O(\tfrac{d}{\varepsilon}\log\tfrac{1}{\varepsilon})$的$\varepsilon$网，具体上界为$\tfrac{d}{\varepsilon}\ln\tfrac{1}{\varepsilon}+\tfrac{2d}{\varepsilon}\ln\ln\tfrac{1}{\varepsilon}+\tfrac{6d}{\varepsilon}$。证明存在小$\varepsilon$网的主要方法是，先拣选$O(\tfrac{d}{\varepsilon}\log\tfrac{1}{\varepsilon})$个点的随机样本$x$，再独立拣选另$O(\tfrac{d}{\varepsilon}\log^2\tfrac{1}{\varepsilon})$个点的随机样本$y$，然后证明以下的不等式：存在某个较大事件$E$与$x$不交的概率$p_1$，与存在同样的事件，且该事件与$y$相交点数大于中位值的概率$p_2$，两概率之比至多为$2$。若固定$E$和$x \cup y$，则$x$不交$E$而$y$与$E$相交点数多于中位值的概率很小。由绍尔-谢拉赫引理，$E$与$x \cup y$的交集的可能情况并不太多，计算“存在$E$满足条件”的概率时，只需对每种交集的可能性考虑一个$E$，因此由并集上界，可得$p_1 \le 2p_2 < 1$，故$x$有非零概率为$\varepsilon$网。

以上论证说明随机取样足够多个点就可能是$\varepsilon$网。此性质以及$\varepsilon$网、$\varepsilon$近似两概念本身，皆在机器学习和概率近似正确学习方面有应用。计算几何方面的应用则有范围搜索、去随机化、近似算法。

利用绍尔-谢拉赫引理的推广，证明若干图论结果，例如：图的强定向为每条边选定一方向，使全幅图强连通。方案数介于其连通子图数与边k连通子图数之间。