En matemáticas combinatorias y teoría de conjuntos extremos , el lema de Sauer-Shelah establece que cada familia de conjuntos con pequeña dimensión VC consta de un pequeño número de conjuntos. Lleva el nombre de Norbert Sauer y Saharon Shelah , quienes lo publicaron de forma independiente en 1972. [1] [2] El mismo resultado también fue publicado un poco antes y nuevamente de forma independiente, por Vladimir Vapnik y Alexey Chervonenkis , de quienes surgió la dimensión VC. es nombrado. [3] En su artículo que contiene el lema, Shelah da crédito también a Micha Perles , [2] y por esta razón el lema también ha sido llamado lema de Perles-Sauer-Shelah y lema de Sauer-Shelah-Perles . [4] [5]
Buzaglo et al. Llame a este lema "uno de los resultados más fundamentales en la dimensión VC", [4] y tiene aplicaciones en muchas áreas. La motivación de Sauer estaba en la combinatoria de sistemas de conjuntos, mientras que la de Shelah estaba en la teoría de modelos y la de Vapnik y Chervonenkis estaba en la estadística . También se ha aplicado en geometría discreta [6] y teoría de grafos . [7]
Definiciones y declaración
Si es una familia de conjuntos y es un conjunto, entonces se dice que está destrozado si cada subconjunto de (incluido el conjunto vacío y él mismo) puede obtenerse como la intersección de con algún conjunto de la familia. La dimensión VC de es la cardinalidad más grande de un conjunto destrozado por .
En términos de estas definiciones, el lema de Sauer-Shelah establece que si es una familia de conjuntos cuya unión tiene elementos, y si el número de conjuntos de la familia, obedece a la desigualdad
El límite del lema es estricto: Sea la familia compuesta por todos los subconjuntos de tamaño menor que . Entonces el tamaño de es exacto pero no destroza ningún conjunto de tamaño . [8]
El número de conjuntos destrozados
Un fortalecimiento del lema de Sauer-Shelah, debido a Pajor (1985), afirma que cada familia de conjuntos finitos destruye al menos conjuntos. [9] Esto implica inmediatamente el lema de Sauer-Shelah, porque sólo los subconjuntos de un universo de elementos tienen cardinalidad menor que . Así, cuando
Para un tipo restringido de conjunto destrozado, llamado conjunto de orden destrozado, el número de conjuntos destrozados siempre es igual a la cardinalidad de la familia de conjuntos. [10]
Prueba
La variante de Pajor del lema de Sauer-Shelah puede demostrarse mediante inducción matemática ; la prueba ha sido atribuida a Noga Alon [11] o a Ron Aharoni y Ron Holzman. [10]
Base
Cada familia de un solo conjunto destruye el conjunto vacío.
Paso
Supongamos que el lema es cierto para todas las familias de tamaño menor que y sea una familia de dos o más conjuntos. Sea un elemento que pertenece a algunos, pero no a todos, los conjuntos de . Dividido en dos subfamilias, de los conjuntos que contienen y de los conjuntos que no contienen . Según el supuesto de inducción, estas dos subfamilias rompen dos colecciones de conjuntos cuyos tamaños suman al menos . Ninguno de estos conjuntos destrozados contiene , ya que un conjunto que contiene no puede ser destrozado por una familia en la que todos los conjuntos contienen o todos los conjuntos no contienen . Algunos de los conjuntos destrozados pueden ser destrozados por ambas subfamilias. Cuando un conjunto es destrozado por sólo una de las dos subfamilias, contribuye con una unidad tanto al número de conjuntos destrozados de la subfamilia como al número de conjuntos destrozados de . Cuando un conjunto es destrozado por ambas subfamilias, ambas y son destrozadas por , por lo que contribuye con dos unidades al número de conjuntos destrozados de las subfamilias y de . Por lo tanto, el número de conjuntos destrozados es al menos igual al número de destrozados por las dos subfamilias de , que es al menos .
La aplicación original del lema, por parte de Vapnik y Chervonenkis, fue mostrar que toda distribución de probabilidad puede aproximarse (con respecto a una familia de eventos de una dimensión de VC dada) mediante un conjunto finito de puntos muestrales cuya cardinalidad depende sólo de la VC. dimensión de la familia de eventos. En este contexto, hay dos nociones importantes de aproximación, ambas parametrizadas por un número : se dice que un conjunto de muestras, y una distribución de probabilidad de , es una aproximación de la distribución original si la probabilidad de cada evento con respecto a difiere de su probabilidad original en como máximo . Se dice que un conjunto de muestras (no ponderadas) es un -net si cada evento con probabilidad incluye al menos un punto de . Una aproximación también debe ser neta, pero no necesariamente al revés.
Vapnik y Chervonenkis utilizaron el lema para demostrar que los sistemas conjuntos de dimensión VC siempre tienen aproximaciones de cardinalidad.
^ Sauer, N. (1972), "Sobre la densidad de familias de conjuntos", Journal of Combinatorial Theory , Serie A, 13 : 145–147, doi :10.1016/0097-3165(72)90019-2, MR 0307902.
^ ab Shelah, Saharon (1972), "Un problema combinatorio; estabilidad y orden de modelos y teorías en lenguajes infinitos", Pacific Journal of Mathematics , 41 : 247–261, doi : 10.2140/pjm.1972.41.247 , MR 0307903, archivado desde el original el 2013-10-05.
^ Vapnik, VN ; Červonenkis, A. Ja. (1971), "La convergencia uniforme de las frecuencias de aparición de eventos con sus probabilidades", Akademija Nauk SSSR , 16 : 264–279, MR 0288823.
^ ab Buzaglo, Sarit; Pinchasi, Rom; Rote, Günter (2013), "Hipergrafos topológicos", en Pach, János (ed.), Treinta ensayos sobre teoría de grafos geométricos , Springer, págs. 71–81, doi :10.1007/978-1-4614-0110-0_6.
^ ab Cambie, Stijn; Chornomaz, Bogdan; Dvir, Zeev; Filmus, Yuval; Moran, Shay (2020), "Un lema de Sauer-Shelah-Perles para celosías", Electronic Journal of Combinatorics , 27 (4): P4.19, arXiv : 1807.04957 , doi : 10.37236/9273.
^ abcd Pach, János ; Agarwal, Pankaj K. (1995), Geometría combinatoria, Serie Wiley-Interscience en Matemáticas Discretas y Optimización, Nueva York: John Wiley & Sons Inc., p. 247, doi :10.1002/9781118033203, ISBN0-471-58890-3, SEÑOR 1354145.
^ ab Kozma, László; Moran, Shay (2013), "Rotura, orientaciones de gráficos y conectividad", Electronic Journal of Combinatorics , 20 (3), P44, arXiv : 1211.1319 , Bibcode : 2012arXiv1211.1319K, MR 3118952.
^ ab Gowers, Timothy (31 de julio de 2008), "Argumentos de dimensión en combinatoria", Weblog de Gowers: debates relacionados con las matemáticas , ejemplo 3.
^ Pajor, Alain (1985), Sous-espaces des espaces de Banach , Travaux en Cours [Obras en curso], vol. 16, París: Hermann, ISBN2-7056-6021-6, SEÑOR 0903247. Citado por Anstee, Rónyai y Sali (2002).
^ ab Anstee, RP; Rónyai, Lajos; Sali, Attila (2002), "Noticias devastadoras", Gráficos y combinatoria , 18 (1): 59–73, doi :10.1007/s003730200003, MR 1892434.
^ Kalai, Gil (28 de septiembre de 2008), "Combinatoria extrema III: algunos teoremas básicos", Combinatoria y más.
^ Blumer, Anselmo; Ehrenfeucht, Andrzej; Haussler, David ; Warmuth, Manfred K. (1989), "La capacidad de aprendizaje y la dimensión Vapnik-Chervonenkis", Journal of the ACM , 36 (4): 929–965, doi : 10.1145/76359.76371 , MR 1072253.
^ Chazelle, B .; Friedman, J. (1990), "Una visión determinista del muestreo aleatorio y su uso en geometría", Combinatorica , 10 (3): 229–249, doi :10.1007/BF02122778, MR 1092541.
^ Brönnimann, H.; Goodrich, MT (1995), "Cubiertas de conjuntos casi óptimos en dimensiones finitas de VC", Geometría discreta y computacional , 14 (4): 463–479, doi : 10.1007/BF02570718 , MR 1360948.
^ Har-Peled, Sariel (2011), "Sobre la complejidad, el muestreo y las redes y muestras", Algoritmos de aproximación geométrica , Encuestas y monografías matemáticas, vol. 173, Providence, RI: Sociedad Matemática Estadounidense, págs. 61–85, ISBN978-0-8218-4911-8, señor 2760023.