---
_id: '1688'
abstract:
- lang: eng
  text: '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.'
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.
article_processing_charge: No
arxiv: 1
author:
- first_name: Roman
  full_name: Karasev, Roman
  last_name: Karasev
- first_name: Jan
  full_name: Kynčl, Jan
  last_name: Kynčl
- first_name: Pavel
  full_name: Paták, Pavel
  last_name: Paták
- first_name: Zuzana
  full_name: Patakova, Zuzana
  last_name: Patakova
  orcid: 0000-0002-3975-1683
- first_name: Martin
  full_name: Tancer, Martin
  id: 38AC689C-F248-11E8-B48F-1D18A9856A87
  last_name: Tancer
  orcid: 0000-0002-1191-6714
citation:
  ama: 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. <i>Discrete &#38; Computational
    Geometry</i>. 2015;54(3):610-636. doi:<a href="https://doi.org/10.1007/s00454-015-9720-z">10.1007/s00454-015-9720-z</a>
  apa: Karasev, R., Kynčl, J., Paták, P., Patakova, Z., &#38; Tancer, M. (2015). Bounds
    for Pach’s selection theorem and for the minimum solid angle in a simplex. <i>Discrete
    &#38; Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/s00454-015-9720-z">https://doi.org/10.1007/s00454-015-9720-z</a>
  chicago: 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.”
    <i>Discrete &#38; Computational Geometry</i>. Springer, 2015. <a href="https://doi.org/10.1007/s00454-015-9720-z">https://doi.org/10.1007/s00454-015-9720-z</a>.
  ieee: 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,” <i>Discrete &#38;
    Computational Geometry</i>, vol. 54, no. 3. Springer, pp. 610–636, 2015.
  ista: 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 &#38;
    Computational Geometry. 54(3), 610–636.
  mla: Karasev, Roman, et al. “Bounds for Pach’s Selection Theorem and for the Minimum
    Solid Angle in a Simplex.” <i>Discrete &#38; Computational Geometry</i>, vol.
    54, no. 3, Springer, 2015, pp. 610–36, doi:<a href="https://doi.org/10.1007/s00454-015-9720-z">10.1007/s00454-015-9720-z</a>.
  short: R. Karasev, J. Kynčl, P. Paták, Z. Patakova, M. Tancer, Discrete &#38; Computational
    Geometry 54 (2015) 610–636.
date_created: 2018-12-11T11:53:28Z
date_published: 2015-10-01T00:00:00Z
date_updated: 2025-09-23T08:02:35Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s00454-015-9720-z
external_id:
  arxiv:
  - '1403.8147'
  isi:
  - '000360702400004'
fulldoi: https://doi.org/10.1007/s00454-015-9720-z
intvolume: '        54'
isi: 1
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1403.8147
month: '10'
oa: 1
oa_version: Preprint
page: 610 - 636
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '5457'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Bounds for Pach's selection theorem and for the minimum solid angle in a simplex
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 54
year: '2015'
...