Separation with restricted families of sets

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:144

Article

Langi, Zsolt¹  Naszodi, Marton^2,3  Pach, Janos^2,4  Tardos, Gabor⁴  Toth, Geza^1,4 

[1] Tech Univ Budapest, Budapest, Hungary

[2] Ecole Polytech Fed Lausanne, Lausanne, Switzerland

[3] Eotvos Lorand Univ, Budapest, Hungary

[4] Renyi Inst, Budapest, Hungary

关键词: Search theory;    Separation;    VC-dimension;    Erdos-Szekeres theorem;   

DOI  :  10.1016/j.jcta.2016.06.002

来源: Elsevier

【 摘 要 】

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.

【 授权许可】

Free