Title: Improved Bounds for Point Selections and Halving Hyperplanes in Higher Dimensions

Speaker: Natan Rubin, Ben Gurion University.

Date and time: 6pm (New York time), Tuesday, April 9, 2024

Place: WWH1314 (room 1314 Warren Weaver Hall, 251 Mercer Street)

...and on Zoom, details on the seminar mailing list

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 {P\choose d+1}$ is a collection of $\varepsilon{n\choose d+1}$ $d$-dimensional simplices with vertices in $P$, for $0<\varepsilon\leq 1$. We show that there is a point $x\in \mathbb{R}^d$ that pierces $\Omega\left(\varepsilon^{(d^4+d)(d+1)+\delta}{n\choose d+1}\right)$ simplices in $E$, for any fixed $\delta>0$. This is a dramatic improvement in all dimensions $d\geq 3$, over the previous lower bounds of the general form $\varepsilon^{(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 $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 $O\left(n^{d-\frac{1}{(2d)^{d}}}\right)$ in all dimensions $d\geq 5$.

An essential ingredient of our proof is the following semi-algebraic Turán-type result of independent interest: Let $(V_1,\ldots,V_k,E)$ be a hypergraph of bounded semi-algebraic description complexity in $\mathbb{R}^d$ that satisfies $|E|\geq \varepsilon |V_1|\cdot\ldots \cdot |V_k|$ for some $\varepsilon>0$. Then there exist subsets $W_i\subseteq V_i$ that satisfy $W_1\times W_2\times\ldots\times W_k\subseteq E$, and $|W_1|\cdot\ldots\cdots|W_k|=\Omega\left(\varepsilon^{d(k-1)+1}|V_1|\cdot |V_2|\cdot\ldots\cdot|V_k|\right)$.