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 $\lvert Y_i\rvert \geq \frac{1}{poly(m)}\lvert X_i\rvert$ such that, for $y_1\in Y_1,\dotsc,y_m\in Y_m$, the orientations of the\linebreak $(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.
@article{10_37236_12414,
author = {Boris Bukh and Alexey Vasileuski},
title = {New bounds for the same-type lemma},
journal = {The electronic journal of combinatorics},
year = {2024},
volume = {31},
number = {2},
doi = {10.37236/12414},
zbl = {1545.52010},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12414/}
}
TY - JOUR
AU - Boris Bukh
AU - Alexey Vasileuski
TI - New bounds for the same-type lemma
JO - The electronic journal of combinatorics
PY - 2024
VL - 31
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/12414/
DO - 10.37236/12414
ID - 10_37236_12414
ER -
%0 Journal Article
%A Boris Bukh
%A Alexey Vasileuski
%T New bounds for the same-type lemma
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/12414/
%R 10.37236/12414
%F 10_37236_12414
Boris Bukh; Alexey Vasileuski. New bounds for the same-type lemma. The electronic journal of combinatorics, Tome 31 (2024) no. 2. doi: 10.37236/12414
