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.