Crossing patterns of semi-algebraic sets

DOI10.1016/J.JCTA.2004.12.008MaRDI QIDQ2566809zbMATH OpenOpenAlexFDO

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

Publication date 28 September 2005

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcta.2004.12.008

Borsuk-Ulam theorem Ramsey theory range searching real algebraic geometry

Ramsey theory (05D10) Semialgebraic sets and related spaces (14P10) Fixed points and coincidences in algebraic topology (55M20)

Review text

A real semialgebraic set in \({\mathbb R}^d\) is described as a finite boolean combination of polynomial equalities and inequalities. The description complexity of such a set is at most \(k\) if in some representation the number of equalities and inequalities is at most \(k\), and each polynomial appearing in the representation has degree at most \(k\). The authors prove that for every family \(\mathcal F\) of \(n\) semialgebraic sets in \({\mathbb R}^d\) there exists a positive constant \(\epsilon\) that depends on the maximum description complexity of the elements of \(\mathcal F\), and two subfamilies \({\mathcal F}_1, {\mathcal F}_2 \subset {\mathcal F}\) with at least \(\epsilon n\) elements each, such that either every element of \({\mathcal F}_1\) intersects all elements of \({\mathcal F}_2\) or no element of \({\mathcal F}_1\) intersects any element of \({\mathcal F}_2\). Moreover, the authors prove this result when the intersection relation is substituted by any other semialgebraic relation. The proof of this result uses a standard linearization process to transform the elements of \(\mathcal F\) into vectors of a higher dimensional space, see the paper of \textit{P. K. Agarwal} and \textit{J. Matousek} [Discrete Comput. Geom. 11, 393--418 (1994; Zbl 0806.68106)] and the partition theorem of \textit{Yao} and \textit{Yao} [in: Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 163--168 (1983)]. The authors also give a second proof using the results of Agarwal and Matousek on range searching with semialgebraic sets. A useful corollary of the main result is the existence of a constant \(\delta\), which depends only on the maximum description complexity of the elements of \(\mathcal F\), such that \(\mathcal F\) has a subset \({\mathcal F}'\) with \(n^\delta\) elements, so that every pair of elements of \({\mathcal F}'\) intersect each other or the elements of \({\mathcal F}'\) are pairwise disjoint. These results are applied to several problems in discrete geometry and in Ramsey theory.

Recommendations

Cites work

Cited in

(69)

This page was built for publication: Crossing patterns of semi-algebraic sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2566809)