紹爾-謝拉赫引理

紹爾-謝拉赫引理，經帕約爾推廣的版本：對於每個有限族（綠色），都存在同樣多個集合組成的另一族（藍色），使得藍色族中每個集合，都被綠色族「打碎」。

組合數學和極值集合論中，紹爾-謝拉赫引理（英語：Sauer–Shelah lemma）斷言，若集合族的VC維低，則該族不能有太多個集合。引理得名於諾貝特·紹爾和薩哈龍·謝拉赫，兩人分別獨立於1972年發表此結果。較之略早，在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$元集。

打碎多少集合

帕約爾將紹爾-謝拉赫引理加強為：

有限族${\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$定義：

1. 取樣集$S$上的概率分佈定義為原分佈的「$\varepsilon$近似」（英語：$\varepsilon$-approximation），意思是每個事件被$S$以該分佈取樣的概率，與原概率所差不過$\varepsilon$。
2. 取樣集$S$（不設權重）定義為「ε網」，意思是概率不小於$\varepsilon$的任一事件中，必含$S$中至少一點。

由定義，$\varepsilon$近似必為$\varepsilon$網，反之則不一定。

VC二氏以此引理證明，若某集族的VC維為$d$，則必有大小不過$O({\tfrac {d}{\varepsilon ^{2}}}\log {\tfrac {d}{\varepsilon }})$的$\varepsilon$近似。其後，Haussler & Welzl (1987)和Komlós, Pach & Woeginger (1992)等發表了類似的結果，證明必存在大小為$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}\leq 2p_{2}<1$，故$x$有非零概率為$\varepsilon$網。

以上論證說明隨機取樣足夠多個點就可能是$\varepsilon$網。此性質以及$\varepsilon$網、$\varepsilon$近似兩概念本身，皆在機器學習和概率近似正確學習方面有應用。計算幾何方面的應用則有範圍搜索、去隨機化、近似算法。

Kozma & Moran (2013)利用紹爾-謝拉赫引理的推廣，證明若干圖論結果，例如：圖的強定向方案數介於其連通子圖數與邊雙連通子圖數之間。