| Tartalom: |
http://real.mtak.hu/26392/ |
| Archívum: |
MTA Könyvtár |
| Gyűjtemény: |
Status = Submitted
Type = Article
|
| Cím: |
Separation with restricted families of sets
|
| Létrehozó: |
Lángi, Zsolt
Naszódi, Márton
Pach, János
Tardos, Gábor
Tóth, Géza
|
| Dátum: |
2015-08-30
|
| Téma: |
QA73 Geometry / geometria
|
| Tartalmi leírás: |
Given a finite n-element 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 Vapnik-Chervonenkis dimension and separation of point sets in R^d
by convex sets are also considered.
|
| Típus: |
Article
NonPeerReviewed
|
| Formátum: |
text
|
| Azonosító: |
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 0097-3165 (Submitted)
|
| Kapcsolat: |
|
