Crossing patterns of semi-algebraic sets

Noga Alon, János Pach, Rom Pinchasi, Radoš Radoičić, Micha Sharir

Research output: Contribution to journalArticlepeer-review

65 Scopus citations

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 F1, F2 ⊆ F with at least εn elements each, such that either every element of F1 intersects all elements of F2 or no element of F1 intersects any element of F2. 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 languageEnglish (US)
Pages (from-to)310-326
Number of pages17
JournalJournal of Combinatorial Theory. Series A
Volume111
Issue number2
DOIs
StatePublished - Aug 2005

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

Fingerprint Dive into the research topics of 'Crossing patterns of semi-algebraic sets'. Together they form a unique fingerprint.

Cite this