Teorema de Bondy

Limita el número de elementos necesarios para distinguir los conjuntos en una familia de conjuntos.

En matemáticas, el teorema de Bondy es un límite en el número de elementos necesarios para distinguir los conjuntos de una familia de conjuntos entre sí. Pertenece al campo de la combinatoria y recibe su nombre de John Adrian Bondy , quien lo publicó en 1972. ^[1]

Declaración

El teorema es el siguiente:

Sea X un conjunto con n elementos y sean A ₁ , A ₂ , ..., A _n subconjuntos distintos de X. Entonces existe un subconjunto S de X con n  − 1 elementos tal que los conjuntos A _i  ∩  S son todos distintos.

En otras palabras, si tenemos una matriz 0-1 con n filas y n columnas de modo que cada fila es distinta, podemos eliminar una columna de modo que las filas de la matriz n  × ( n  − 1) resultante sean distintas. ^{[2] [3]}

Ejemplo

Considere la matriz 4 × 4

${\displaystyle {\begin{bmatrix}1&1&0&1\\0&1&0&1\\0&0&1&1\\0&1&1&0\end{bmatrix}}}$

donde todas las filas son distintas por pares. Si eliminamos, por ejemplo, la primera columna, la matriz resultante

${\displaystyle {\begin{bmatrix}1&0&1\\1&0&1\\0&1&1\\1&1&0\end{bmatrix}}}$

Ya no tiene esta propiedad: la primera fila es idéntica a la segunda. Sin embargo, por el teorema de Bondy sabemos que siempre podemos encontrar una columna que se pueda eliminar sin introducir ninguna fila idéntica. En este caso, podemos eliminar la tercera columna: todas las filas de la matriz 3 × 4

${\displaystyle {\begin{bmatrix}1&1&1\\0&1&1\\0&0&1\\0&1&0\end{bmatrix}}}$

son distintas. Otra posibilidad hubiera sido eliminar la cuarta columna.

Aplicación de la teoría del aprendizaje

Desde la perspectiva de la teoría del aprendizaje computacional , el teorema de Bondy puede reformularse de la siguiente manera: ^[4]

Sea C una clase de concepto sobre un dominio finito X . Entonces existe un subconjunto S de X con un tamaño como máximo | C | − 1 tal que S es un conjunto testigo para cada concepto en C .

Esto implica que cada clase de concepto finito C tiene su dimensión de enseñanza limitada por | C | − 1.

Notas

1. Bondy, JA (1972), "Subconjuntos inducidos", Journal of Combinatorial Theory, Serie B , 12 (2): 201–202, doi : 10.1016/0095-8956(72)90025-1 , MR  0319773.
2. Jukna, Stasys (2001), Combinatoria extrema con aplicaciones en informática , Springer, ISBN 978-3-540-66313-3, Sección 12.1.
3. Clote, Peter; Remmel, Jeffrey B. (1995), Matemáticas factibles II , Birkhäuser, ISBN 978-3-7643-3675-2, Sección 4.1.
4. Kushilevitz, Eyal; Linial, Nathan; Rabinovich, Yuri; Saks, Michael (1996), "Conjuntos testigo para familias de vectores binarios", Journal of Combinatorial Theory , Serie A, 73 (2): 376–380, doi : 10.1016/S0097-3165(96)80015-X , MR  1370141.