Bounds for Pach's selection theorem and for the minimum solid angle in a simplex
We estimate the selection constant in the following geometric selection theorem by Pach: For every positive integer d there is a constant cd>0 such that whenever X1,...,Xd+1 are n-element subsets of Rd, then we can find a point p∈Rd and subsets Yi⊆Xi for every i∈[d+1], each of size at least cdn, such that p belongs to all {\em rainbow} d-simplices determined by Y1,...,Yd+1, that is, simplices with one vertex in each Yi. We show a super-exponentially decreasing upper bound cd≤e−(1/2−o(1))(dlnd). The ideas used in the proof of the upper bound also help us prove Pach's theorem with cd≥2−2d2+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 cd≥2−O(d2logd). 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 2d separations in the original proof. We also provide a measure version of Pach's theorem.