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.{{Citation
| last=Bondy | first=J. A. | authorlink=John Adrian Bondy
| title=Induced subsets
| journal=Journal of Combinatorial Theory, Series B
| volume=12
| year=1972
| issue=2 | pages=201–202
| doi=10.1016/0095-8956(72)90025-1
| mr=0319773
| doi-access=free
}}.
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.{{citation
| first=Stasys | last=Jukna
| title=Extremal Combinatorics with Applications in Computer Science
| publisher=Springer
| year=2001
| isbn=978-3-540-66313-3
Example
Consider the 4 × 4 matrix
:
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
\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
\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:{{citation
| last1 = Kushilevitz | first1 = Eyal
| last2 = Linial | first2 = Nathan
| last3 = Rabinovich | first3 = Yuri
| last4 = Saks | first4 = Michael
| doi = 10.1016/S0097-3165(96)80015-X
| issue = 2
| journal = Journal of Combinatorial Theory
| mr = 1370141
| pages = 376–380
| series = Series A
| title = Witness sets for families of binary vectors
| volume = 73
| year = 1996| doi-access = free
}}.
: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.