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
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
where all rows are pairwise distinct. If we delete, for example, the first column, the resulting matrix
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
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.