## Abstract

We prove that, for every family F of n semi-algebraic sets in ℝ^{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.

Original language | English (US) |
---|---|

Pages (from-to) | 310-326 |

Number of pages | 17 |

Journal | Journal of Combinatorial Theory. Series A |

Volume | 111 |

Issue number | 2 |

DOIs | |

State | Published - Aug 2005 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## Keywords

- Borsuk-Ulam theorem
- Crossing patterns
- Ramsey theory
- Range searching
- Real algebraic geometry