تقرير
New bounds for the same-type lemma
| العنوان: | New bounds for the same-type lemma |
|---|---|
| المؤلفون: | Bukh, Boris, Vasileuski, Alexey |
| سنة النشر: | 2023 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics |
| الوصف: | Given finite sets $X_1,\dotsc,X_m$ in $\mathbb{R}^d$ (with $d$ fixed), we prove that there are respective subsets $Y_1,\dotsc,Y_m$ with $|Y_i|\ge \frac{1}{\operatorname{poly}(m)}|X_i|$ such that, for $y_1\in Y_1,\dotsc,y_m\in Y_m$, the orientations of the $(d+1)$-tuples from $y_1,\dotsc,y_m$ do not depend on the actual choices of points $y_1,\dotsc,y_m$. This generalizes previously known case when all the sets $X_i$ are equal. Furthermore, we give a construction showing that polynomial dependence on $m$ is unavoidable, as well as an algorithm that approximates the best-possible constants in this result. Comment: 9 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2309.10731 |
| رقم الأكسشن: | edsarx.2309.10731 |
| قاعدة البيانات: | arXiv |
كن أول من يترك تعليقا!