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.

Statement

The theorem is as follows:
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 × 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:
This implies that every finite concept class C has its teaching dimension bounded by |C| − 1.