Teorema de Bondy

Teorema de Bondy Em matemática, O teorema de Bondy é um limite no número de elementos necessários para distinguir os conjuntos em uma família de conjuntos uns dos outros. Pertence ao campo da combinatória, e é nomeado após John Adrian Bondy, que publicou em 1972.[1] Conteúdo 1 Declaração 2 Exemplo 3 Aplicação da teoria de aprendizagem 4 Notes Statement The theorem is as follows: Seja X um conjunto com n elementos e seja A1, A2, ..., Um ser subconjuntos distintos de X. Then there exists a subset S of X with n − 1 elements such that the sets Ai ∩ S are all distinct.

Em outras palavras, se tivermos um 0-1 matriz com n linhas e n colunas tal que cada linha é distinta, we can remove one column such that the rows of the resulting n × (n - 1) matriz são distintas.[2][3] Example Consider the 4 × 4 matriz {estilo de exibição {começar{bmatriz}1&1&0&1\0&1&0&1\0&0&1&1\0&1&1&0end{bmatriz}}} onde todas as linhas são distintas aos pares. se nós apagarmos, por exemplo, a primeira coluna, a matriz resultante {estilo de exibição {começar{bmatriz}1&0&1\1&0&1\0&1&1\1&1&0end{bmatriz}}} não tem mais essa propriedade: a primeira linha é idêntica à segunda linha. No entanto, pelo teorema de Bondy sabemos que sempre podemos encontrar uma coluna que pode ser excluída sem introduzir nenhuma linha idêntica. Nesse caso, podemos excluir a terceira coluna: all rows of the 3 × 4 matriz {estilo de exibição {começar{bmatriz}1&1&1\0&1&1\0&0&1\0&1&0end{bmatriz}}} são distintos. Outra possibilidade seria deletar a quarta coluna.

Learning theory application From the perspective of computational learning theory, O teorema de Bondy pode ser reformulado da seguinte forma:[4] Seja C uma classe de conceito sobre um domínio finito X. Então existe um subconjunto S de X com o tamanho no máximo |C| − 1 such that S is a witness set for every concept in C.

Isso implica que toda classe de conceito finito C tem sua dimensão de ensino limitada por |C| − 1.

Notas ^ Bondy, J. UMA. (1972), "Subconjuntos induzidos", Jornal de Teoria Combinatória, Série B, 12: 201-202, doi:10.1016/0095-8956(72)90025-1, SENHOR 0319773. ^ Yukna, Estase (2001), Combinatória Extrema com Aplicações em Ciência da Computação, Springer, ISBN 978-3-540-66313-3, Seção 12.1. ^ Cloto, Peter; Reme, Jeffrey B. (1995), Matemática Viável II, Birkhauser, ISBN 978-3-7643-3675-2, Seção 4.1. ^ Kushilevitz, Eyal; linear, Natan; Rabinovich, Yuri; Saks, Michael (1996), "Conjuntos de testemunhas para famílias de vetores binários", Jornal de Teoria Combinatória, Série A, 73 (2): 376-380, doi:10.1016/S0097-3165(96)80015-X, SENHOR 1370141. Categorias: Teoria da aprendizagem computacionalTeoremas em combinatória