绍尔-谢拉赫引理
若集合族的VC維低,則不能有太多個集合 / 维基百科,自由的 encyclopedia
组合数学和极值集合论(英语:extremal set theory)中,绍尔-谢拉赫引理(英语:Sauer–Shelah lemma)断言,若集合族的VC维低,则该族不能有太多个集合。引理得名于诺贝特·绍尔[1]和萨哈龙·谢拉赫(英语:Saharon Shelah)[2],两人分别独立于1972年发表此结果。[注 1]较之略早,在1971年,弗拉基米尔·瓦普尼克和亚历克塞·泽范兰杰斯合著的论文[6]已有此结果(“VC维”即以两人为名)。谢拉赫发表引理时,亦归功于米哈·佩尔莱斯(英语:Micha Perles),故引理又称为佩尔莱斯-绍尔-谢拉赫引理。[7]
布萨格洛等人称其为“关于VC维的最根本结论之一”[7]。引理在若干方面有应用,就各发现者的研究动机而言,绍尔是研究集族的组合学,谢拉赫研究模型论,VC二氏则研究统计学。后来,引理亦用于离散几何[8]和图论[9]。