紹爾-謝拉赫引理

組合數學和極值集合論中，**紹爾 - 謝拉赫引理**（英語：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) 利用紹爾 - 謝拉赫引理的推廣，證明若干圖論結果，例如：圖的強定向方案數介於其連通子圖數與邊雙連通子圖數之間。

## 註

## 參考文獻