Vapnik-Chervonekis-Sauer-Shelah Lemmaともいう．いわゆる極値組合せ論の定理．機械学習のVC次元等に応用がある（らしい）．
集合 $E$ の部分集合族 $\mathcal{F}$ が集合 $S \subseteq E$ を shutter するとは，任意の $X \subseteq S$ に対して $S \cap F = X$ となる $F \in \mathcal{F}$ が存在するときにいう．
Vapnik-Chervonekis-Sauer-Shelah Lemma
$\mathcal{F}$ が $|\mathcal{F}| > \binom{n}{0} + \dots + \binom{n}{k} $ を満たすならば，$\mathcal{F}$ にshutterされる $S$ で $|S| \geq k+1$ となるものが存在する．
[証明] すこしだけ強い次の主張（Pajorによる）を示す:
Claim: 任意の集合族 $\mathcal{F}$ は 少なくとも $|\mathcal{F}|$ 個の集合をshutterする．
これは $n=|E|$ に関する帰納法で示せる．$n=1$のときは自明．$n > 1$ とし，$e \in E$ を任意に固定する．
\begin{align}
\mathcal{F}_1 &:= \{F \in \mathcal{F} : e \notin F\}, \\
\mathcal{F}_2 &:= \{F\setminus e : F \in \mathcal{F}, e \in F\}
\end{align}
とする．すると，帰納法の仮定から $\mathcal{F}_i$ は少なくとも $|\mathcal{F}_i|$ 個の $E\setminus e$の部分集合をshutterする．
また，$\mathcal{F}_1$と$\mathcal{F}_2$の両方にshutterされる $S \subseteq E \setminus e$ を考えると，$\mathcal{F}$ は $S \cup e$ をshutterすることが確認できる．よって，数え上げの議論によって $\mathcal{F}$ は少なくとも $|\mathcal{F}_1| + |\mathcal{F}_2| = |\mathcal{F}|$ 個の集合をshutterする．■
参考:
