组合数学和中，紹爾-謝拉赫引理（）斷言，若集合族的VC维低，則該族不能有太多個集合。引理得名於諾貝特·紹爾和，兩人分別獨立於1972年發表此結果。較之略早，在1971年，弗拉基米尔·瓦普尼克和亞歷克塞·澤范蘭傑斯合著的論文已有此結果（「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元集。
打碎多少集合
帕约尔將紹爾-謝拉赫引理加強為：{{refn| 由
證
紹爾-謝拉赫引理的帕約爾變式可使用数学归纳法證明，此證法一說出自諾加·阿隆，一說出自及朗·霍爾茲曼（）和等發表了類似的結果，證明必存在大小為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}。计算几何方面的應用則有、近似算法。
利用紹爾-謝拉赫引理的推廣，證明若干圖論結果，例如：圖的方案數介於其連通子圖數與子圖數之間。
註
參考文獻
评论 (0)