Lema de Sauer-Shela

Noción en combinatoria

Formulación de Pajor del lema de Sauer-Shelah: para cada familia finita de conjuntos (verde) hay otra familia de igual número de conjuntos (contornos azules) de modo que cada conjunto de la segunda familia es destrozado por la primera familia

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 . ${\displaystyle \textstyle {\mathcal {F}}=\{S_{1},S_{2},\dots \}}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle T\cap S_{i}}$ ${\displaystyle T}$ ${\displaystyle S_{i}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$

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 ${\displaystyle {\mathcal {F}}}$ ${\displaystyle n}$ ${\displaystyle |{\mathcal {F}}|}$

$${\displaystyle |{\mathcal {F}}|>\sum _{i=0}^{k-1}{\binom {n}{i}},}$$

${\displaystyle {\mathcal {F}}}$ ${\displaystyle k}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle k,}$ ${\displaystyle {\mathcal {F}}}$

$${\displaystyle \sum _{i=0}^{k}{\binom {n}{i}}=O(n^{k})}$$

la notación O grande

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] ${\displaystyle {\mathcal {F}}}$ ${\displaystyle \{1,2,\dots ,n\}}$ ${\displaystyle k}$ ${\displaystyle {\mathcal {F}}}$ ${\textstyle \sum _{i=0}^{k-1}{\binom {n}{i}}}$ ${\displaystyle k}$

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 ${\displaystyle {\mathcal {F}}}$ ${\displaystyle |{\mathcal {F}}|}$ ${\textstyle \sum _{i=0}^{k-1}{\tbinom {n}{i}}}$ ${\displaystyle n}$ ${\displaystyle k}$

$${\displaystyle |{\mathcal {F}}|>\sum _{i=0}^{k-1}{\tbinom {n}{i}},}$$

${\displaystyle k}$

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 . ${\displaystyle |{\mathcal {F}}|}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle x}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle |{\mathcal {F}}|}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S\cup \{x\}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle |{\mathcal {F}}|}$

Una prueba diferente del lema de Sauer-Shelah en su forma original, realizada por Péter Frankl y János Pach , se basa en el álgebra lineal y el principio de inclusión-exclusión . ^{[6] [8]} Esta prueba se extiende a otros entornos, como familias de espacios vectoriales y, más en general, redes geométricas . ^[5]

Aplicaciones

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. ${\displaystyle \varepsilon }$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle \varepsilon }$ ${\displaystyle S}$ ${\displaystyle \varepsilon }$ ${\displaystyle S}$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$ ${\displaystyle S}$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$

Vapnik y Chervonenkis utilizaron el lema para demostrar que los sistemas conjuntos de dimensión VC siempre tienen aproximaciones de cardinalidad. ${\displaystyle d}$ ${\displaystyle \varepsilon }$

$${\displaystyle O({\tfrac {d}{\varepsilon ^{2}}}\log {\tfrac {d}{\varepsilon }}).}$$

^{[12][13],[6].} ${\displaystyle \varepsilon }$ ${\displaystyle O({\tfrac {d}{\varepsilon }}\log {\tfrac {1}{\varepsilon }})}$

$${\displaystyle {\tfrac {d}{\varepsilon }}\ln {\tfrac {1}{\varepsilon }}+{\tfrac {2d}{\varepsilon }}\ln \ln {\tfrac {1}{\varepsilon }}+{\tfrac {6d}{\varepsilon }}.}$$

unión ligada^[6] ${\displaystyle \varepsilon }$ ${\displaystyle x}$ ${\textstyle O({\tfrac {d}{\varepsilon }}\log {\tfrac {1}{\varepsilon }})}$ ${\displaystyle y}$ ${\textstyle O({\tfrac {d}{\varepsilon }}\log ^{2}{\tfrac {1}{\varepsilon }})}$ ${\displaystyle x}$ ${\displaystyle E}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\cup y}$ ${\displaystyle E}$ ${\displaystyle x}$ ${\displaystyle \varepsilon }$

A su vez, las redes y las aproximaciones, y la probabilidad de que una muestra aleatoria de cardinalidad suficientemente grande tenga estas propiedades, tienen aplicaciones importantes en el aprendizaje automático , en el área del aprendizaje probablemente aproximadamente correcto . ^[14] En geometría computacional , se han aplicado a la búsqueda de rangos , ^[12] desrandomización , ^[15] y algoritmos de aproximación . ^{[16] [17]} ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$

Kozma y Moran (2013) utilizan generalizaciones del lema de Sauer-Shelah para demostrar resultados en teoría de grafos , como que el número de orientaciones fuertes de un gráfico determinado se intercala entre su número de subgrafos conectados y conectados por 2 aristas . ^[7]

Ver también

• Función de crecimiento

Referencias

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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, ISBN 0-471-58890-3, SEÑOR  1354145.
7. 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.
8. Gowers, Timothy (31 de julio de 2008), "Argumentos de dimensión en combinatoria", Weblog de Gowers: debates relacionados con las matemáticas , ejemplo 3.
9. Pajor, Alain (1985), Sous-espaces des espaces de Banach , Travaux en Cours [Obras en curso], vol. 16, París: Hermann, ISBN ${\displaystyle l_{1}^{n}}$ 2-7056-6021-6, SEÑOR  0903247. Citado por Anstee, Rónyai y Sali (2002).
10. Anstee, RP; Rónyai, Lajos; Sali, Attila (2002), "Noticias devastadoras", Gráficos y combinatoria , 18 (1): 59–73, doi :10.1007/s003730200003, MR  1892434.
11. Kalai, Gil (28 de septiembre de 2008), "Combinatoria extrema III: algunos teoremas básicos", Combinatoria y más.
12. abHaussler, David ; Welzl, Emo (1987), " -redes y consultas de rango simplex", Geometría computacional y discreta , 2 (2): 127–151, doi : 10.1007/BF02187876 , SEÑOR  0884223 ${\displaystyle \varepsilon }$.
13. Komlós, János ; Pach, János ; Woeginger, Gerhard (1992), "Límites casi estrechos para redes", Geometría discreta y computacional , 7 (2): 163–173, doi : 10.1007/BF02187833 , MR  1139078 ${\displaystyle \varepsilon }$.
14. 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.
15. 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.
16. 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.
17. 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, ISBN ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$ 978-0-8218-4911-8, señor  2760023.