Teoremas sobre la perforación de números

Question

Estoy buscando resultados relacionados con los números de los piercings. Un ejemplo de lo que estoy buscando es este teorema: cualquier Clase VC que es k-consistente tiene un número de perforación acotado.

Sin embargo, la búsqueda en Google/arxiv sólo me da el teorema anterior y un montón de artículos sobre conjuntos convexos. ¿Cuáles son otros resultados/documentos relacionados con los números perforantes? Lo ideal sería que fueran de naturaleza combinatoria y no geométrica.

Antecedentes: Pregunto esto porque actualmente estoy investigando sobre la posible conexión entre las Clases VC y los esquemas de compresión.

Answer 1

Uno de los resultados más generales es el de Alon y Kalai en su informe de 1995 documento " Limitado el número de perforaciones ," resolviendo los 1957 " $(p,q)$ problema" de Hadwiger y Debrunner. El espectáculo que, si existe una familia de conjuntos $\cal F$ (condición de estos conjuntos más adelante) para que cualquier $p$ de ellos contienen un subconjunto de $q$ con una intersección no vacía, $p \ge q$ , entonces existe un conjunto de como máximo $c$ puntos que intersectan cada miembro de $\cal F$ es decir, $c$ puntos de perforación $\cal F$ . La condición sobre $\cal F$ es que cada miembro es la unión de como máximo $k$ compactos, conjuntos convexos en $\mathbb{R}^d$ . Por supuesto $c$ depende de todos los parámetros $\lbrace p, q, k, d \rbrace$ pero lo importante es que $c$ es finito. Este es un resultado geométrico, más que puramente combinatorio, pero es muy amplio. Geometría discreta y computacional , Vol. 13, No. 1, 245-236, 1995 .

También puede consultar el "Teorema de Caratheodory de colores", descrito, por ejemplo, en Blog de Gil Kalai .

Answer 2

El resultado que buscas está demostrado en el artículo de Matousek "bounded VC-dimension implies a fractional Helly theorem". Es el teorema 4.

Matousek explica cómo adaptar la prueba de Alon y Kleitman del $(p,q)$ -teorema mencionado en la respuesta de Joseph de familias de conjuntos convexos a familias de dimensión VC finita.