Théorème de Bondy

Théorème de Bondy En mathématiques, Le théorème de Bondy est une borne sur le nombre d'éléments nécessaires pour distinguer les ensembles d'une famille d'ensembles les uns des autres. Il appartient au domaine de la combinatoire, et porte le nom de John Adrian Bondy, qui l'a publié dans 1972.[1] Contenu 1 Déclaration 2 Exemple 3 Application de la théorie de l'apprentissage 4 Notes Statement The theorem is as follows: Soit X un ensemble à n éléments et soit A1, A2, ..., An être des sous-ensembles distincts de X. Then there exists a subset S of X with n − 1 elements such that the sets Ai ∩ S are all distinct.

Autrement dit, si nous avons un 0-1 matrice à n lignes et n colonnes telle que chaque ligne soit distincte, we can remove one column such that the rows of the resulting n × (n- 1) matrice sont distincts.[2][3] Example Consider the 4 × 4 matrice {style d'affichage {commencer{bmatrice}1&1&0&1\0&1&0&1\0&0&1&1\0&1&1&0end{bmatrice}}} où toutes les lignes sont distinctes deux à deux. Si nous supprimons, par exemple, la première colonne, la matrice résultante {style d'affichage {commencer{bmatrice}1&0&1\1&0&1\0&1&1\1&1&0end{bmatrice}}} n'a plus cette propriété: la première rangée est identique à la deuxième rangée. Néanmoins, par le théorème de Bondy, nous savons que nous pouvons toujours trouver une colonne qui peut être supprimée sans introduire de lignes identiques. Dans ce cas, nous pouvons supprimer la troisième colonne: all rows of the 3 × 4 matrice {style d'affichage {commencer{bmatrice}1&1&1\0&1&1\0&0&1\0&1&0end{bmatrice}}} sont distincts. Une autre possibilité aurait été de supprimer la quatrième colonne.

Learning theory application From the perspective of computational learning theory, Le théorème de Bondy peut être reformulé comme suit:[4] Soit C une classe de concepts sur un domaine fini X. Alors il existe un sous-ensemble S de X de taille au plus |C| − 1 such that S is a witness set for every concept in C.

Cela implique que chaque classe de concepts finis C a sa dimension d'enseignement délimitée par |C| − 1.

Remarques ^ Bondy, J. UN. (1972), "Sous-ensembles induits", Journal de théorie combinatoire, Série B, 12: 201–202, est ce que je:10.1016/0095-8956(72)90025-1, M 0319773. ^ Yukna, Stase (2001), Combinatoire extrême avec applications en informatique, Springer, ISBN 978-3-540-66313-3, Section 12.1. ^ Cloé, Pierre; Remme, Jeffrey B.. (1995), Mathématiques réalisables II, Birkhauser, ISBN 978-3-7643-3675-2, Section 4.1. ^ Kushilevitz, Eyal; linéaire, Nath; Rabinovitch, Youri; Saks, Michael (1996), "Ensembles de témoins pour les familles de vecteurs binaires", Journal de théorie combinatoire, Série A, 73 (2): 376–380, est ce que je:10.1016/S0097-3165(96)80015-X, M 1370141. Catégories: Théorie de l'apprentissage informatiqueThéorèmes en combinatoire