Separation with restricted families of sets

Given a finite n-element set X  , a family of subsets F⊂2XF⊂2X is said to separate X if any two elements of X   are separated by at least one member of FF. It is shown that if |F|>2n−1|F|>2n−1, then one can select ⌈log⁡n⌉+1⌈log⁡n⌉+1 members of FF that separate X  . If |F|≥α2n|F|≥α2n for some 0<α<1/20<α<1/2, then log⁡n+O(log⁡1αlog⁡log⁡1α) members of FF are always sufficient to separate all pairs of elements of X   that are separated by some member of FF. 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 RdRd by convex sets are also considered.