Misplaced Pages

Bondy's theorem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
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 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

[ 1 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0 ] {\displaystyle {\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

[ 1 0 1 1 0 1 0 1 1 1 1 0 ] {\displaystyle {\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

[ 1 1 1 0 1 1 0 0 1 0 1 0 ] {\displaystyle {\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:

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

  1. Bondy, J. A. (1972), "Induced subsets", Journal of Combinatorial Theory, Series B, 12 (2): 201–202, doi:10.1016/0095-8956(72)90025-1, MR 0319773.
  2. Jukna, Stasys (2001), Extremal Combinatorics with Applications in Computer Science, Springer, ISBN 978-3-540-66313-3, Section 12.1.
  3. Clote, Peter; Remmel, Jeffrey B. (1995), Feasible Mathematics II, Birkhäuser, ISBN 978-3-7643-3675-2, Section 4.1.
  4. 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: