绍尔-谢拉赫引理

组合数学和极值集合论（英语：extremal set theory）中，绍尔-谢拉赫引理（英语：Sauer–Shelah lemma）断言，若集合族的VC维低，则该族不能有太多个集合。引理得名于诺贝特·绍尔^[1]和萨哈龙·谢拉赫（英语：Saharon Shelah）^[2]，两人分别独立于1972年发表此结果。^{[注 1]}较之略早，在1971年，弗拉基米尔·瓦普尼克和亚历克塞·泽范兰杰斯合著的论文^[6]已有此结果（“VC维”即以两人为名）。谢拉赫发表引理时，亦归功于米哈·佩尔莱斯（英语：Micha Perles），故引理又称为佩尔莱斯-绍尔-谢拉赫引理。^[7]

绍尔-谢拉赫引理，经帕约尔推广的版本：对于每个有限族（绿色），都存在同样多个集合组成的另一族（蓝色），使得蓝色族中每个集合，都被绿色族“打碎（英语：shattered set）”。

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

定义及叙述

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

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

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

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

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

打碎多少集合

帕约尔将绍尔-谢拉赫引理加强为：^[12]

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

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

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

证

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

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

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

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

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

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

绍尔-谢拉赫引理的原始形式还有另一种证明，利用线性代数及容斥原理，该证法由弗龙克尔·彼得（英语：Péter Frankl）和保奇·亚诺什（英语：János Pach）给出。^[8][10]

应用

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

1. 取样集${\displaystyle S}$上的概率分布定义为原分布的“${\displaystyle \varepsilon }$近似”（英语：${\displaystyle \varepsilon }$-approximation），意思是每个事件被${\displaystyle S}$以该分布取样的概率，与原概率所差不过${\displaystyle \varepsilon }$。
2. 取样集${\displaystyle S}$（不设权重）定义为“ε网（英语：ε-net (computational geometry)）”，意思是概率不小于${\displaystyle \varepsilon }$的任一事件中，必含${\displaystyle S}$中至少一点。

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

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

以上论证说明随机取样足够多个点就可能是${\displaystyle \varepsilon }$网。此性质以及${\displaystyle \varepsilon }$网、${\displaystyle \varepsilon }$近似两概念本身，皆在机器学习和概率近似正确学习（英语：probably approximately correct learning）方面有应用。^[16]计算几何方面的应用则有范围搜索（英语：range searching）^[14]、去随机化（英语：derandomization）^[17]、近似算法^[18][19]。

Kozma & Moran (2013)利用绍尔-谢拉赫引理的推广，证明若干图论结果，例如：图的强定向（英语：strong orientation）^{[注 2]}方案数介于其连通子图数与边双连通（英语：k-edge-connected graph）子图数之间。^[9]