Improved Bounds for Point Selections and Halving Hyperplanes in Higher Dimensions
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909124974870528 |
|---|---|
| author | Rubin, Natan |
| author_facet | Rubin, Natan |
| contents | 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 $ε{n\choose d+1}$ $d$-dimensional simplices with vertices in $P$, for $0<ε\leq 1$. We show that there is a point $x\in {\mathbb R}^d$ that pierces $\displaystyle Ω\left(ε^{(d^4+d)(d+1)+δ}{n\choose d+1}\right)$ simplices in $E$, for any fixed $δ>0$. This is a dramatic improvement in all dimensions $d\geq 3$, over the previous lower bounds of the general form $\displaystyle ε^{(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)}+δ}\right)$ halving hyperplanes, for any $δ>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\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|=Ω\left(\varepsilon^{d(k-1)+1}|V_1|\cdot |V_2|\cdot\ldots\cdot|V_k|\right)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_00412 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved Bounds for Point Selections and Halving Hyperplanes in Higher Dimensions Rubin, Natan Combinatorics Computational Geometry 52A35, 52C35, 52C45, 05D10, 05C65 G.2.1; G.2.2; F.2.2 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 $ε{n\choose d+1}$ $d$-dimensional simplices with vertices in $P$, for $0<ε\leq 1$. We show that there is a point $x\in {\mathbb R}^d$ that pierces $\displaystyle Ω\left(ε^{(d^4+d)(d+1)+δ}{n\choose d+1}\right)$ simplices in $E$, for any fixed $δ>0$. This is a dramatic improvement in all dimensions $d\geq 3$, over the previous lower bounds of the general form $\displaystyle ε^{(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)}+δ}\right)$ halving hyperplanes, for any $δ>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\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|=Ω\left(\varepsilon^{d(k-1)+1}|V_1|\cdot |V_2|\cdot\ldots\cdot|V_k|\right)$. |
| title | Improved Bounds for Point Selections and Halving Hyperplanes in Higher Dimensions |
| topic | Combinatorics Computational Geometry 52A35, 52C35, 52C45, 05D10, 05C65 G.2.1; G.2.2; F.2.2 |
| url | https://arxiv.org/abs/2403.00412 |