# Bondy's theorem

Bondy's theorem In mathematics, Bondy's theorem is a bound on the number of elements needed to distinguish the sets in a family of sets from each other. It belongs to the field of combinatorics, and is named after John Adrian Bondy, who published it in 1972. Contents 1 Statement 2 Example 3 Learning theory application 4 Notes Statement The theorem is as follows: Let X be a set with n elements and let A1, A2, ..., An be distinct subsets of X. Then there exists a subset S of X with n − 1 elements such that the sets Ai ∩ S are all distinct.

In other words, if we have a 0-1 matrix with n rows and n columns such that each row is distinct, we can remove one column such that the rows of the resulting n × (n − 1) matrix are distinct. Example Consider the 4 × 4 matrix {displaystyle {begin{bmatrix}1&1&0&1\0&1&0&1\0&0&1&1\0&1&1&0end{bmatrix}}} where all rows are pairwise distinct. If we delete, for example, the first column, the resulting matrix {displaystyle {begin{bmatrix}1&0&1\1&0&1\0&1&1\1&1&0end{bmatrix}}} no longer has this property: the first row is identical to the second row. Nevertheless, by Bondy's theorem we know that we can always find a column that can be deleted without introducing any identical rows. In this case, we can delete the third column: all rows of the 3 × 4 matrix {displaystyle {begin{bmatrix}1&1&1\0&1&1\0&0&1\0&1&0end{bmatrix}}} are distinct. Another possibility would have been deleting the fourth column.

Learning theory application From the perspective of computational learning theory, Bondy's theorem can be rephrased as follows: Let C be a concept class over a finite domain X. Then there exists a subset S of X with the size at most |C| − 1 such that S is a witness set for every concept in C.

This implies that every finite concept class C has its teaching dimension bounded by |C| − 1.

Notes ^ Bondy, J. A. (1972), "Induced subsets", Journal of Combinatorial Theory, Series B, 12: 201–202, doi:10.1016/0095-8956(72)90025-1, MR 0319773. ^ Jukna, Stasys (2001), Extremal Combinatorics with Applications in Computer Science, Springer, ISBN 978-3-540-66313-3, Section 12.1. ^ Clote, Peter; Remmel, Jeffrey B. (1995), Feasible Mathematics II, Birkhäuser, ISBN 978-3-7643-3675-2, Section 4.1. ^ Kushilevitz, Eyal; Linial, Nathan; Rabinovich, Yuri; Saks, Michael (1996), "Witness sets for families of binary vectors", Journal of Combinatorial Theory, Series A, 73 (2): 376–380, doi:10.1016/S0097-3165(96)80015-X, MR 1370141. Categories: Computational learning theoryTheorems in combinatorics

Si quieres conocer otros artículos parecidos a Bondy's theorem puedes visitar la categoría Computational learning theory.

Subir

Utilizamos cookies propias y de terceros para mejorar la experiencia de usuario Más información