Crossing patterns of semi-algebraic sets

We prove that, for every family F of n semi-algebraic sets in R d of constant description complexity, there exist a positive constant ɛ that depends on the maximum complexity of the elements of F , and two subfamilies F 1 , F 2 ⊆ F with at least ɛ n elements each, such that either every element of F 1 intersects all elements of F 2 or no element of F 1 intersects any element of F 2 . This implies the existence of another constant δ such that F has a subset F ′ ⊆ F with n δ 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.