Bondy's theorem

Short description: Bounds the number of elements needed to distinguish the sets in a family of sets

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:

Let X be a set with n elements and let A₁, A₂, ..., A_n be distinct subsets of X. Then there exists a subset S of X with n − 1 elements such that the sets A_i ∩ 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

[math]\displaystyle{ \begin{bmatrix} 1&1&0&1\\ 0&1&0&1\\ 0&0&1&1\\ 0&1&1&0 \end{bmatrix} }[/math]

where all rows are pairwise distinct. If we delete, for example, the first column, the resulting matrix

[math]\displaystyle{ \begin{bmatrix} 1&0&1\\ 1&0&1\\ 0&1&1\\ 1&1&0 \end{bmatrix} }[/math]

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

[math]\displaystyle{ \begin{bmatrix} 1&1&1\\ 0&1&1\\ 0&0&1\\ 0&1&0 \end{bmatrix} }[/math]

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.