Crossing patterns of semi-algebraic sets

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:111

Article

Alon, N ; Pach, J ; Pinchasi, R ; Radoicic, R ; Sharir, M

关键词: crossing patterns;    Borsuk-Ulam theorem;    real algebraic geometry;    range searching;    Ramsey theory;   

DOI  :  10.1016/j.jcta.2004.12.008

来源: Elsevier

【 摘 要 】

We prove that, for every family F of n semi-algebraic sets in R-d of constant description complexity, there exist a positive constant E that depends on the maximum complexity of the elements of F, and two subfamilies F-1, F-2 subset of F with at least En elements each, such that either every element of F-1 intersects all elements of epsilon 2 or no element of F-1 intersects any element Of F2. This implies the existence of another constant delta such that F has a subset F` subset of F with n(delta) elements, so that either every pair of elements of F' intersect each other or the elements of F' are pairwise disjoint. The same results hold when the intersection relation is replaced by any other semi-algebraic relation. We apply these results to settle several problems in discrete geometry and in Ramsey theory. (c) 2005 Elsevier Inc. All rights reserved.

【 授权许可】

Free