Bondy's theorem explained

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.^[1]

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.^[2] ^[3]

Example

Consider the 4 × 4 matrix

\begin{bmatrix} 1&1&0&1\\ 0&1&0&1\\ 0&0&1&1\\ 0&1&1&0 \end{bmatrix}

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

\begin{bmatrix} 1&0&1\\ 1&0&1\\ 0&1&1\\ 1&1&0 \end{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

\begin{bmatrix} 1&1&1\\ 0&1&1\\ 0&0&1\\ 0&1&0 \end{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:^[4]

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 and References

.
, Section 12.1.
, Section 4.1.
.