تقرير
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 |
كن أول من يترك تعليقا!