Bondy's Theorem

Bondy's theorem, introduced by John Adrian Bondy in 1972, bounds the number of elements needed to distinguish the sets in a family of sets from one another. For a set X of n elements together with n distinct subsets of X, the theorem guarantees a subset S of X with only n minus 1 elements such that intersecting each of the n subsets with S still yields n distinct results, equivalent to being able to delete one column from an n by n binary matrix with distinct rows while keeping every row distinct. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/