Lángi, Zsolt and Naszódi, Márton and Pach, János and Tardos, Gábor and Tóth, Géza (2015) Separation with restricted families of sets. JOURNAL OF COMBINATORIAL THEORY SERIES A. ISSN 00973165 (Submitted)

Text
separation.pdf Download (207kB)  Preview 
Abstract
Given a finite nelement set X, a family of subsets F ⊂ 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 F > 2^(n−1), then one can select ⌈log n⌉ + 1 members of F that separate X. If F ≥ m2^n for some 0 < m < 1/2, then log n + O(log 1 /m log log 1/m) 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 VapnikChervonenkis dimension and separation of point sets in R^d by convex sets are also considered.
Item Type:  Article 

Subjects:  Q Science / természettudomány > QA Mathematics / matematika > QA73 Geometry / geometria 
Depositing User:  Dr. Zsolt Lángi 
Date Deposited:  11 Sep 2015 10:52 
Last Modified:  11 Sep 2015 11:07 
URI:  http://real.mtak.hu/id/eprint/26392 
Actions (login required)
Edit Item 