Bounds for Pach's Selection Theorem and for the Minimum Solid Angle in a Simplex.
Saved in:
| Title: | Bounds for Pach's Selection Theorem and for the Minimum Solid Angle in a Simplex. |
|---|---|
| Authors: | Karasev, Roman r_n_karasev@mail.ru, Kynčl, Jan kyncl@kam.mff.cuni.cz, Paták, Pavel1 patak@kam.mff.cuni.cz, Patáková, Zuzana2 zuzka@kam.mff.cuni.cz, Tancer, Martin tancer@kam.mff.cuni.cz |
| Source: | Discrete & Computational Geometry. Oct2015, Vol. 54 Issue 3, p610-636. 27p. |
| Subjects: | Selection theorems, Combinatorial set theory, Topological spaces, Mathematics theorems, Computational geometry |
| Abstract: | We estimate the selection constant in the following geometric selection theorem by Pach: For every positive integer d, there is a constant $$c_d > 0$$ such that whenever $$X_1, \ldots , X_{d+1}$$ are n-element subsets of $$\mathbb {R}^d$$ , we can find a point $${\mathbf {p}}\in \mathbb {R}^d$$ and subsets $$Y_i \subseteq X_i$$ for every $$i \in [d+1]$$ , each of size at least $$c_d n$$ , such that $${\mathbf {p}}$$ belongs to all rainbow d-simplices determined by $$Y_1, \ldots , Y_{d+1}$$ , i.e., simplices with one vertex in each $$Y_i$$ . We show a super-exponentially decreasing upper bound $$c_d\le e^{-(1/2-o(1))(d \ln d)}$$ . The ideas used in the proof of the upper bound also help us to prove Pach's theorem with $$c_d \ge 2^{-2^{d^2 + O(d)}}$$ , 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 $$c_d \ge 2^{-O(d^2\log d)}$$ . 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 $$2^d$$ separations in the original proof. We also provide a measure version of Pach's theorem. [ABSTRACT FROM AUTHOR] |
| Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 109236933 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Bounds for Pach's Selection Theorem and for the Minimum Solid Angle in a Simplex. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Karasev%2C+Roman%22">Karasev, Roman</searchLink><i> r_n_karasev@mail.ru</i><br /><searchLink fieldCode="AR" term="%22Kynčl%2C+Jan%22">Kynčl, Jan</searchLink><i> kyncl@kam.mff.cuni.cz</i><br /><searchLink fieldCode="AR" term="%22Paták%2C+Pavel%22">Paták, Pavel</searchLink><relatesTo>1</relatesTo><i> patak@kam.mff.cuni.cz</i><br /><searchLink fieldCode="AR" term="%22Patáková%2C+Zuzana%22">Patáková, Zuzana</searchLink><relatesTo>2</relatesTo><i> zuzka@kam.mff.cuni.cz</i><br /><searchLink fieldCode="AR" term="%22Tancer%2C+Martin%22">Tancer, Martin</searchLink><i> tancer@kam.mff.cuni.cz</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Discrete+%26+Computational+Geometry%22">Discrete & Computational Geometry</searchLink>. Oct2015, Vol. 54 Issue 3, p610-636. 27p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Selection+theorems%22">Selection theorems</searchLink><br /><searchLink fieldCode="DE" term="%22Combinatorial+set+theory%22">Combinatorial set theory</searchLink><br /><searchLink fieldCode="DE" term="%22Topological+spaces%22">Topological spaces</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematics+theorems%22">Mathematics theorems</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+geometry%22">Computational geometry</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: We estimate the selection constant in the following geometric selection theorem by Pach: For every positive integer d, there is a constant $$c_d > 0$$ such that whenever $$X_1, \ldots , X_{d+1}$$ are n-element subsets of $$\mathbb {R}^d$$ , we can find a point $${\mathbf {p}}\in \mathbb {R}^d$$ and subsets $$Y_i \subseteq X_i$$ for every $$i \in [d+1]$$ , each of size at least $$c_d n$$ , such that $${\mathbf {p}}$$ belongs to all rainbow d-simplices determined by $$Y_1, \ldots , Y_{d+1}$$ , i.e., simplices with one vertex in each $$Y_i$$ . We show a super-exponentially decreasing upper bound $$c_d\le e^{-(1/2-o(1))(d \ln d)}$$ . The ideas used in the proof of the upper bound also help us to prove Pach's theorem with $$c_d \ge 2^{-2^{d^2 + O(d)}}$$ , 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 $$c_d \ge 2^{-O(d^2\log d)}$$ . 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 $$2^d$$ separations in the original proof. We also provide a measure version of Pach's theorem. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=109236933 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s00454-015-9720-z Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 27 StartPage: 610 Subjects: – SubjectFull: Selection theorems Type: general – SubjectFull: Combinatorial set theory Type: general – SubjectFull: Topological spaces Type: general – SubjectFull: Mathematics theorems Type: general – SubjectFull: Computational geometry Type: general Titles: – TitleFull: Bounds for Pach's Selection Theorem and for the Minimum Solid Angle in a Simplex. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Karasev, Roman – PersonEntity: Name: NameFull: Kynčl, Jan – PersonEntity: Name: NameFull: Paták, Pavel – PersonEntity: Name: NameFull: Patáková, Zuzana – PersonEntity: Name: NameFull: Tancer, Martin IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 10 Text: Oct2015 Type: published Y: 2015 Identifiers: – Type: issn-print Value: 01795376 Numbering: – Type: volume Value: 54 – Type: issue Value: 3 Titles: – TitleFull: Discrete & Computational Geometry Type: main |
| ResultId | 1 |
