Improved Bounds for Point Selections and Halving Hyperplanes in Higher Dimensions

Let $(P,E)$ be a $(d+1)$-uniform geometric hypergraph, where $P$ is an $n$-point set in general position in ${\mathbb{R}}^d$ and $E\subseteq \left(\genfrac{}{}{0px}{}{P}{d+1}\right)$ is a collection of $\epsilon \left(\genfrac{}{}{0px}{}{n}{d+1}\right)$ $d$-dimensional simplices with vertices in $P$, for $0<\epsilon \le 1$. We show that there is a point $x\in {\mathbb{R}}^d$ that pierces ${\displaystyle \mathrm{\Omega }\left({\epsilon }^{(d^4+d)(d+1)+\delta }\left(\genfrac{}{}{0px}{}{n}{d+1}\right)\right)}$ simplices in $E$, for any fixed $\delta >0$. This is a dramatic improvement in all dimensions $d\ge 3$, over the previous lower bounds of the general form ${\displaystyle {\epsilon }^{(cd{)}^{d+1}}{n}^{d+1}}$, which date back to the seminal 1991 work of Alon, Bárány, Füredi and Kleitman. As a result, any $n$-point set in general position in ${\mathbb{R}}^d$ admits only ${\displaystyle O\left(n^{d-\frac{1}{d(d-1{)}^4+d(d-1)}+\delta }\right)}$ halving hyperplanes, for any $\delta >0$, which is a significant improvement over the previously best known bound ${\displaystyle O\left(n^{d-\frac{1}{(2d{)}^d}}\right)}$ in all dimensions $d\ge 5$. An essential ingredient of our proof is the following semi-algebraic Turán-type result of independent interest: Let $(V_1,\dots ,V_k,E)$ be a hypergraph of bounded semi-algebraic description complexity in ${\mathbb{R}}^d$ that satisfies $\mathrm{\mid }E\mathrm{\mid }\ge \epsilon \mathrm{\mid }{V}_1\mathrm{\mid }\cdot \dots \cdot \mathrm{\mid }{V}_k\mathrm{\mid }$ for some $\epsilon >0$. Then there exist subsets $W_i\subseteq V_i$ that satisfy $W_1\times W_2\times \dots \times W_k\subseteq E$, and $\mathrm{\mid }{W}_1\mathrm{\mid }\cdot \dots \cdots \mathrm{\mid }{W}_k\mathrm{\mid }=\mathrm{\Omega }({\epsilon }^{d(k-1)+1}\mathrm{\mid }{V}_1\mathrm{\mid }\cdot \mathrm{\mid }{V}_2\mathrm{\mid }\cdot \dots \cdot \mathrm{\mid }{V}_k\mathrm{\mid })$.