Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Bounds for Pach's Selection Theorem and for the Minimum Solid Angle in a Simplex
 
research article

Bounds for Pach's Selection Theorem and for the Minimum Solid Angle in a Simplex

Karasev, Roman
•
Kyncl, Jan  
•
Patak, Pavel
Show more
2015
Discrete & Computational Geometry

We estimate the selection constant in the following geometric selection theorem by Pach: For every positive integer d, there is a constant such that whenever are n-element subsets of , we can find a point and subsets for every , each of size at least , such that belongs to all rainbow d-simplices determined by , i.e., simplices with one vertex in each . We show a super-exponentially decreasing upper bound . The ideas used in the proof of the upper bound also help us to prove Pach's theorem with , 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 . 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 separations are necessary, compared to separations in the original proof. We also provide a measure version of Pach's theorem.

  • Details
  • Metrics
Type
research article
DOI
10.1007/s00454-015-9720-z
Web of Science ID

WOS:000360702400004

Author(s)
Karasev, Roman
Kyncl, Jan  
Patak, Pavel
Patakova, Zuzana
Tancer, Martin
Date Issued

2015

Publisher

Springer

Published in
Discrete & Computational Geometry
Volume

54

Issue

3

Start page

610

End page

636

Subjects

Pach's selection theorem

•

d-Dimensional simplex

•

Solid angle

•

Borel probability measure

•

Weak convergence of measures

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Available on Infoscience
September 28, 2015
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/118672
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés