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.


Published in:
Journal Of Combinatorial Theory Series A, 144, 292-305
Year:
2016
Publisher:
San Diego, Academic Press Inc Elsevier Science
ISSN:
0097-3165
Keywords:
Laboratories:




 Record created 2016-10-18, last modified 2018-01-28


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)