紹爾-謝拉赫引理：修订间差异
删除的内容 添加的内容
（没有差异）
|
2022年3月6日 (日) 23:15的版本
 | 此條目目前正依照en:Sauer–Shelah lemma上的内容进行翻译。 (2022年3月6日) |
组合数学和極值集合論中，紹爾-謝拉赫引理（英語：Sauer–Shelah lemma）斷言，若集合族的VC维低，則該族不能有太多個集合。引理得名於諾貝特·紹爾[1]和薩哈龍·謝拉赫[2]，兩人分別獨立於1972年發表此結果。較之略早，在1971年，弗拉基米尔·瓦普尼克和亞歷克塞·澤范蘭傑斯合著的論文[3]已有此結果（「VC維」即以兩人為名）。謝拉赫發表引理時，亦歸功於米哈·佩爾萊斯，故引理又稱為佩爾萊斯-紹爾-謝拉赫引理。[4]
布萨格洛等人稱其為「關於VC維的最根本結論之一」[4]。引理在許多方面有應用，就各發現者的研究動機而言，紹爾是研究集族的組合學，謝拉赫研究模型论，VC二氏則研究统计学。後來，引理亦用於离散几何[5]和图论[6]。
參考文獻
- ^ Sauer, N. On the density of families of sets. Journal of Combinatorial Theory. Series A. 1972, 13: 145–147. MR 0307902. doi:10.1016/0097-3165(72)90019-2
.
- ^ Shelah, Saharon. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics. 1972, 41: 247–261. MR 0307903. doi:10.2140/pjm.1972.41.247 . （原始内容存档于2013-10-05）.
- ^ Vapnik, V. N.; Červonenkis, A. Ja. The uniform convergence of frequencies of the appearance of events to their probabilities. Akademija Nauk SSSR. 1971, 16: 264–279. MR 0288823.
- ^ 4.0 4.1 Buzaglo, Sarit; Pinchasi, Rom; Rote, Günter. Topological hypergraphs. Pach, János (编). Thirty Essays on Geometric Graph Theory. Springer. 2013: 71–81. doi:10.1007/978-1-4614-0110-0_6 .
- ^ Pach, János; Agarwal, Pankaj K. Combinatorial geometry. Wiley-Interscience Series in Discrete Mathematics and Optimization. New York: John Wiley & Sons Inc.: 247. 1995. ISBN 0-471-58890-3. MR 1354145. doi:10.1002/9781118033203 .
- ^ Kozma, László; Moran, Shay. Shattering, Graph Orientations, and Connectivity. Electronic Journal of Combinatorics. 2013, 20 (3). P44. Bibcode:2012arXiv1211.1319K. arXiv:1211.1319 .
