Teorema de Bondy

En matemàtiques el teorema de Bondy és un teorema de combinatòria que va aparèixer en un article de 1972 de John Adrian Bondy. El teorema diu:

Sia X un conjunt amb n elements i sia A₁, A₂..., A_n subconjunts diferents de X. Llavors existeix un subconjunt S de X amb n-1 elements tal que els conjunts A_i ∩ S són tots diferents.

En altres paraules, si es té una matriu de n files i n columnes tal que cada fila és diferent, es pot treure una columna de forma que les files de la matriu n × (n − 1) que en resulta són diferents.

Des de la perspectiva de la teoria d'aprenentatge computacional, això es pot reformular com esegueix:

Sia C una classe de concepte sobre un domini finit X. Llavors existeix un subconjunt S de X amb la mida com a màxim|C | − 1 tal que S és un conjunt testimoni per a tots els conceptes de C.

Això implica que cada classe de concepte finita C té dimensió d'ènsenyament limitada per|C| − 1.

Exemple

Considereu la matriu de 4 × 4

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

on totes les files són diferents dues a dues. Si es suprimeix, per exemple, la primera columna, la matriu que resulta

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

ja no té aquesta propietat: la primera fila és idèntica a la segona fila. No obstant això, pel teorema de Bondy se sap que sempre es pot trobar una columna que es pot suprimir sense introduir files idèntiques. En aquest cas, es pot suprimir la tercera columna: totes les files de la matriu de 3 × 4

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

són diferents. Una altra possibilitat hauria estat suprimint la quarta columna.