Separation with restricted families of sets

Original · EN

Given a finite n-element set X, a family of subsets F⊂ 2ˣ is said to separate X if any two elements of X are separated by at least one member of F. It is shown that if |F|>2ⁿ⁻¹, then one can select n+1 members of F that separate X. If |F|≥ α2ⁿ for some 0<α<1/2, then n+O(1α1α) members of F are always sufficient to separate all pairs of elements of X that are separated by some member of F. This result is generalized to simultaneous separation in several sets. Analogous questions on separation by families of bounded Vapnik-Chervonenkis dimension and separation of point sets in Rᵈ by convex sets are also considered.