Colorful positive bases decomposition and Helly-type results for cones
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_ | 1866917112716460032 |
|---|---|
| author | Ivanov, Grigory |
| author_facet | Ivanov, Grigory |
| contents | We prove the following colorful Helly-type result: Fix $k \in [d-1]$. Assume $\mathcal{A}_1, \dots, \mathcal{A}_{d+(d-k)+1}$ are finite sets (colors) of nonzero vectors in $\R^d$. If for every rainbow sub-selection $R$ from these sets of size at most $\max \{d+1, 2(d-k+1)\}$, the system $\langle {a},{x} \rangle \leq 0,\; a \in R$ has at least $k$ linearly independent solutions, then at least one of the systems $\langle {a},{x} \rangle \leq 0,\; a \in \mathcal{A}_i,$ $i \in [d+(d-k)+1]$ has at least $k$ linearly independent solutions.
A \emph{rainbow sub-selection} from several sets refers to choosing at most one element from each set (color).
The Helly number $\max \{d+1, 2(d-k+1)\}$ and the number of colors $d+(d-k)+1$ are optimal.
Our key observation is a certain colorful Carathéodory-type result for positive bases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_20961 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Colorful positive bases decomposition and Helly-type results for cones Ivanov, Grigory Combinatorics Metric Geometry 52A35 (primary), 52A30 We prove the following colorful Helly-type result: Fix $k \in [d-1]$. Assume $\mathcal{A}_1, \dots, \mathcal{A}_{d+(d-k)+1}$ are finite sets (colors) of nonzero vectors in $\R^d$. If for every rainbow sub-selection $R$ from these sets of size at most $\max \{d+1, 2(d-k+1)\}$, the system $\langle {a},{x} \rangle \leq 0,\; a \in R$ has at least $k$ linearly independent solutions, then at least one of the systems $\langle {a},{x} \rangle \leq 0,\; a \in \mathcal{A}_i,$ $i \in [d+(d-k)+1]$ has at least $k$ linearly independent solutions. A \emph{rainbow sub-selection} from several sets refers to choosing at most one element from each set (color). The Helly number $\max \{d+1, 2(d-k+1)\}$ and the number of colors $d+(d-k)+1$ are optimal. Our key observation is a certain colorful Carathéodory-type result for positive bases. |
| title | Colorful positive bases decomposition and Helly-type results for cones |
| topic | Combinatorics Metric Geometry 52A35 (primary), 52A30 |
| url | https://arxiv.org/abs/2407.20961 |