New bounds for the same-type lemma
New bounds for the same-type lemma (scientific article; zbMATH DE number 7882981)
Sets \(Y_1,\dots, Y_{d+1}\subset \mathbb{R}^d\) are said to have the \textit{same-type property} if, for every choice of points \(y_1 \in Y_1,\dots, y_{d+1} \in Y_{d+1}\), the orientation of the points \(y_1,\dots, y_{d+1}\) is the same. More generally, the sets \(Y_1,\dots, Y_m \) are said to have the same-type property if every \(d + 1\) of them do. A natural question is the following: given disjoint finite sets \(X_1,\dots ,X_m \subset \mathbb{R}^d\) such that their union is in general position, are there large subsets \(Y_i \subseteq X_i\) such that the sets \(Y_1,\dots, Y_m\) have the same-type property? The same-type lemma proved by \textit{I. Bárány} and \textit{P. Valtr} [Discrete Comput. Geom. 19, No. 3, 335--342 (1998; Zbl 0914.52007)] states that each \(Y_i\) may be taken to have a positive fraction of points from the corresponding \(X_i\). How large could this fraction be? Formally, for disjoint sets \(X_1,\dots ,X_m \subset \mathbb{R}^d\), whose union is in general position, let us denote by \(c(X_1, \dots ,X_m)\) the largest constant \(c\) for which there exist \(Y_1,\dots, Y_m\) having the same-type property and satisfying \(Y_i \subseteq X_i\), \(|Y_i| \geq c|X_i|\). For any fixed number \(m\) and dimension \(d\), denote by \(c(m, d)\) the infimum of \(c\) for all such configurations. The paper under review shows that for \(d\geq 2\) and \(m\geq d\), the constant \(c(m,d)\) depends polynomially from \(m\), if \(d\) is fixed, by showing the bounds \(d^{-50d^3}m^{-d^2}\leq c(m,d)\leq d^dm^{-d}\). In the past, polynomial bounds were known only in the case of equal sized \(X_i\) sets.\N\NAs the same type lemma is frequently used in discrete geometry, this extension is very relevant. A construction is given to show that polynomial dependence on \(m\) is unavoidable. An algorithm is presented to approximate \(c(m, d)\) within a prescribed error.
- A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
- A positive fraction Erdős-Szekeres theorem
- A positive fraction mutually avoiding sets theorem
- A Tverberg-type result on multicolored simplices
- Algorithms in real algebraic geometry
- Crossing patterns of segments
- Erdős-Szekeres theorem for point sets with forbidden subconfigurations
- scientific article; zbMATH DE number 1749054 (Why is no real title available?)
- scientific article; zbMATH DE number 3068536 (Why is no real title available?)
- On the Erdős distinct distances problem in the plane
- On the Erdős-Szekeres convex polygon problem
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
- Space crossing numbers
- The partitioned version of the Erdős-Szekeres theorem
- The probabilistic method
This page was built for publication: New bounds for the same-type lemma
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6574401)
