Lángi, Zsolt and Naszódi, Márton and Pach, J. and Tardos, G. and Tóth, G. (2016) Separation with restricted families of sets. JOURNAL OF COMBINATORIAL THEORY SERIES A, 144. pp. 292305. ISSN 00973165
Text
asAppearedSeparation.pdf  Published Version Restricted to Registered users only Download (401kB)  Request a copy 


Text
40197.pdf  Submitted Version Download (339kB)  Preview 
Abstract
Given a finite nelement set X, a family of subsets F ⊂ 2X 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 F > 2n−1, then one can select [log n] + 1 members of F that separate X. If F ≥ α2n for some 0 < α < 1/2, then log n + O(log 1 α log log 1 α ) members of F are always sufficient to separate all pairs of elements of X that are separated by some member of F. 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 Rd by convex sets are also considered.
Item Type:  Article 

Uncontrolled Keywords:  VCdimension; SEPARATION; Search theory; ErdosSzekeres theorem 
Subjects:  Q Science / természettudomány > QA Mathematics / matematika 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  27 Sep 2016 11:55 
Last Modified:  09 Jan 2017 08:04 
URI:  http://real.mtak.hu/id/eprint/40197 
Actions (login required)
Edit Item 