Bounds for Pach's selection theorem and for the minimum solid angle in a simplex

R. Karasev, J. Kynčl, P. Paták, Z. Patakova, M. Tancer, Discrete & Computational Geometry 54 (2015) 610–636.


Journal Article | Published | English
Author
; ; ; ;
Department
Abstract
We estimate the selection constant in the following geometric selection theorem by Pach: For every positive integer d, there is a constant (Formula presented.) such that whenever (Formula presented.) are n-element subsets of (Formula presented.), we can find a point (Formula presented.) and subsets (Formula presented.) for every i∈[d+1], each of size at least cdn, such that p belongs to all rainbowd-simplices determined by (Formula presented.) simplices with one vertex in each Yi. We show a super-exponentially decreasing upper bound (Formula presented.). The ideas used in the proof of the upper bound also help us to prove Pach’s theorem with (Formula presented.), which is a lower bound doubly exponentially decreasing in d (up to some polynomial in the exponent). For comparison, Pach’s original approach yields a triply exponentially decreasing lower bound. On the other hand, Fox, Pach, and Suk recently obtained a hypergraph density result implying a proof of Pach’s theorem with (Formula presented.). In our construction for the upper bound, we use the fact that the minimum solid angle of every d-simplex is super-exponentially small. This fact was previously unknown and might be of independent interest. For the lower bound, we improve the ‘separation’ part of the argument by showing that in one of the key steps only d+1 separations are necessary, compared to 2d separations in the original proof. We also provide a measure version of Pach’s theorem.
Publishing Year
Date Published
2015-10-01
Journal Title
Discrete & Computational Geometry
Acknowledgement
R. K. was supported by the Russian Foundation for Basic Research Grant 15-31-20403 (mol_a_ved) and grant 15-01-99563. J. K., Z. P., and M. T. were partially supported by ERC Advanced Research Grant No. 267165 (DISCONV) and by the project CE-ITI (GAČR P202/12/G061) of the Czech Science Foundation. J. K. was also partially supported by Swiss National Science Foundation Grants 200021-137574 and 200020-14453. P. P., Z. P., and M. T. were partially supported by the Charles University Grant GAUK 421511. P. P. was also partially supported by the Charles University Grant SVV-2014-260107. Z. P. was also partially supported by the Charles University Grant SVV-2014-260103.
Volume
54
Issue
3
Page
610 - 636
IST-REx-ID

Cite this

Karasev R, Kynčl J, Paták P, Patakova Z, Tancer M. Bounds for Pach’s selection theorem and for the minimum solid angle in a simplex. Discrete & Computational Geometry. 2015;54(3):610-636. doi:10.1007/s00454-015-9720-z
Karasev, R., Kynčl, J., Paták, P., Patakova, Z., & Tancer, M. (2015). Bounds for Pach’s selection theorem and for the minimum solid angle in a simplex. Discrete & Computational Geometry, 54(3), 610–636. https://doi.org/10.1007/s00454-015-9720-z
Karasev, Roman, Jan Kynčl, Pavel Paták, Zuzana Patakova, and Martin Tancer. “Bounds for Pach’s Selection Theorem and for the Minimum Solid Angle in a Simplex.” Discrete & Computational Geometry 54, no. 3 (2015): 610–36. https://doi.org/10.1007/s00454-015-9720-z.
R. Karasev, J. Kynčl, P. Paták, Z. Patakova, and M. Tancer, “Bounds for Pach’s selection theorem and for the minimum solid angle in a simplex,” Discrete & Computational Geometry, vol. 54, no. 3, pp. 610–636, 2015.
Karasev R, Kynčl J, Paták P, Patakova Z, Tancer M. 2015. Bounds for Pach’s selection theorem and for the minimum solid angle in a simplex. Discrete & Computational Geometry. 54(3), 610–636.
Karasev, Roman, et al. “Bounds for Pach’s Selection Theorem and for the Minimum Solid Angle in a Simplex.” Discrete & Computational Geometry, vol. 54, no. 3, Springer, 2015, pp. 610–36, doi:10.1007/s00454-015-9720-z.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar