In mathematics, Bondy's theorem is a theorem in combinatorics that appeared in a 1972 article by John Adrian Bondy. 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.
From the perspective of computational learning theory, this 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.
Read more about Bondy's Theorem: Example
Famous quotes containing the word theorem:
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (19131960)