Crossing patterns of semi-algebraic sets (Q2566809): Difference between revisions

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.