期刊
JOURNAL OF COMBINATORIAL THEORY SERIES A
卷 144, 期 -, 页码 292-305出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jcta.2016.06.002
关键词
Search theory; Separation; VC-dimension; Erdos-Szekeres theorem
类别
资金
- Janos Bolyai Research Scholarship of the Hungarian Academy of Sciences
- National Research, Development, and Innovation Office, NKFIH [PD-104744, K-116769, SNN-117879, K-111827, K-83767]
- Swiss National Science Foundation [200020-162884, 200021-165977]
- Hungarian-Mexican Grant [TET-12-MX-1-2013-0006]
- Cryptography Lendulet project of the Hungarian Academy of Sciences
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据