# 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)$.