Pach's selection theorem does not admit a topological extension

Abstract

Let $U_1,\dots ,U_{d+1}$ be $n$-element sets in $R^d$ and let $⟨u_1,\dots ,u_{d+1}⟩$ denote the convex hull of points $u_i$ in $U_i$ (for all $i$) which is a (possibly degenerate) simplex. Pach's selection theorem says that there are sets $Z_1\subset U_1,\dots ,Z_{d+1}\subset U_{d+1}$ and a point $u$ in $R^d$ such that each $|Z_i|>c_1(d)n$ and $u$ belongs to $⟨z_1,...,z_{d+1}⟩$ for every choice of $z_1$ in $Z_1,\dots ,z_{d+1}$ in $Z_{d+1}$. Here we show that this theorem does not admit a topological extension with linear size sets $Z_i$. However, there is a topological extension where each $|Z_i|$ is of order $(\log n{)}^{(}1/d)$.

arXiv comment8 pages