Separation with restricted families of sets

Given a finite n-element set X, a family of subsets F subset of 2(X) 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 vertical bar F vertical bar > 2(n-1), then one can select vertical bar log n vertical bar + 1 members of T that separate X. If vertical bar F vertical bar >= alpha 2(n) for some 0 < alpha < 1/2, then log n + O(log 1/alpha log log 1/alpha) members of F are always sufficient to separate all pairs of elements of X that are separated by some member of T. 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-d by convex sets are also considered. (C) 2016 Elsevier Inc. All rights reserved.