Tight colorful no-dimensional Tverberg theorem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912605416718336 |
|---|---|
| author | Barabanshchikova, Polina Ivanov, Grigory Polyanskii, Alexander |
| author_facet | Barabanshchikova, Polina Ivanov, Grigory Polyanskii, Alexander |
| contents | We study colorful no-dimensional Tverberg-type problems and obtain several optimal results. A colorful no-dimensional Tverberg-type theorem provides a bound on a radius $R$ such that, for any pairwise disjoint $k$-element subsets $Q_1,\dots,Q_n$ of a normed space, there exists a partition of $Q_1\cup\cdots\cup Q_n$ into disjoint transversals $\{P_1,\dots,P_k\}$ for which a ball of radius $R$ intersects the convex hull of each $P_i$ ($1\le i\le k$). Our methods are deterministic and dimension-free, and they are unified by optimizing two functionals: a quadratic \emph{selection} functional whose local maximizers produce a complete system of disjoint transversals, and a convex \emph{intersection} functional that certifies a common point.
First, in the Euclidean setting we bound $R$ in terms of the Chebyshev radii (minimal enclosing-ball radii) of the color classes $Q_1,\dots,Q_n$. A key observation is a ``combinatorial'' subadditivity of the squared Chebyshev radius: given sequences $X=(x_1,\dots,x_k)$ and $Y=(y_1,\dots,y_k)$ of points in a Euclidean space, contained in balls of radii $R_X$ and $R_Y$ (not necessarily with the same center), one can reenumerate $Y$ so that the pointwise-sum sequence $Z=(x_1+y_1,\dots,x_k+y_k)$ is contained in a ball of radius $R_Z$ satisfying \[ R_Z^2 \le R_X^2 + R_Y^2 . \] As a corollary, we obtain the best-possible bound \[ R \le \frac{1}{\sqrt{2n}}\sqrt{\frac{k-1}{k}}\, \max_{1\le i\le n} \operatorname{diam}(Q_i). \] Our algorithm returns the desired disjoint transversals
in overall time $\mathcal{O}(nk^3)$.
Second, we develop a complementary approach based on the inter-color diameter and extend the framework to obtain no-dimensional colorful Tverberg-type results in the hyperbolic setting and in Banach spaces. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_05814 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tight colorful no-dimensional Tverberg theorem Barabanshchikova, Polina Ivanov, Grigory Polyanskii, Alexander Metric Geometry We study colorful no-dimensional Tverberg-type problems and obtain several optimal results. A colorful no-dimensional Tverberg-type theorem provides a bound on a radius $R$ such that, for any pairwise disjoint $k$-element subsets $Q_1,\dots,Q_n$ of a normed space, there exists a partition of $Q_1\cup\cdots\cup Q_n$ into disjoint transversals $\{P_1,\dots,P_k\}$ for which a ball of radius $R$ intersects the convex hull of each $P_i$ ($1\le i\le k$). Our methods are deterministic and dimension-free, and they are unified by optimizing two functionals: a quadratic \emph{selection} functional whose local maximizers produce a complete system of disjoint transversals, and a convex \emph{intersection} functional that certifies a common point. First, in the Euclidean setting we bound $R$ in terms of the Chebyshev radii (minimal enclosing-ball radii) of the color classes $Q_1,\dots,Q_n$. A key observation is a ``combinatorial'' subadditivity of the squared Chebyshev radius: given sequences $X=(x_1,\dots,x_k)$ and $Y=(y_1,\dots,y_k)$ of points in a Euclidean space, contained in balls of radii $R_X$ and $R_Y$ (not necessarily with the same center), one can reenumerate $Y$ so that the pointwise-sum sequence $Z=(x_1+y_1,\dots,x_k+y_k)$ is contained in a ball of radius $R_Z$ satisfying \[ R_Z^2 \le R_X^2 + R_Y^2 . \] As a corollary, we obtain the best-possible bound \[ R \le \frac{1}{\sqrt{2n}}\sqrt{\frac{k-1}{k}}\, \max_{1\le i\le n} \operatorname{diam}(Q_i). \] Our algorithm returns the desired disjoint transversals in overall time $\mathcal{O}(nk^3)$. Second, we develop a complementary approach based on the inter-color diameter and extend the framework to obtain no-dimensional colorful Tverberg-type results in the hyperbolic setting and in Banach spaces. |
| title | Tight colorful no-dimensional Tverberg theorem |
| topic | Metric Geometry |
| url | https://arxiv.org/abs/2408.05814 |