# Geometry Seminar

#### Improved Bounds for Point Selections and Halving Hyperplanes in Higher Dimensions

Speaker: Natan Rubin, Ben Gurion University

Location: Warren Weaver Hall 1314

Videoconference link: https://youtu.be/sANdjEFyYZk

Date: Tuesday, April 9, 2024, 6 p.m.

Synopsis:

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

Notes:

See mailing list announcements for Zoom details or contact Boris Aronov.