Pushed colorful polytopal KKMS Theorem and orthogonal star transversals
Abstract
A classical theorem of Kaiser and Rabinovich implies that if every subfamily of size at most ⌊log2(d+1)⌋+1 of a finite family of compact connected sets in ℝd has a common axis-parallel hyperplane transversal, then the entire family has an orthogonal star transversal, i.e., a union of d hyperplanes, one perpendicular to each coordinate axis. We study colorful variants of this result. First, we use standard KKM machinery to establish a colorful analogue with d+1 color classes and a ⌊log2(d+1)⌋+1 transversal hypothesis for rainbow subfamiles. Then we focus on reducing the required number of colors. To this end, we introduce the rainbow pushability πr(P) of a polytope and we use it to state and prove few-color variants of the colorful Carathéodory theorem and the colorful polytopal KKMS theorem. Applying the latter to the d-dimensional cube, we show that ⌊log2 d⌋+2 color classes suffice for our transversal problem, provided that every rainbow choice has a common axis-parallel hyperplane transversal. We also extend both colorful results to the setting of convex (n,D)-bodies and we show that three colors are needed for d≥ 2.
Related
- Spanning k-trees and the colorful Carathéodory theorem
- A colorful quantitative Helly theorem for volume
- A colorful Steinitz theorem with different centers
- Multi-graded generic initial ideals, regularity, and the optimal colorful fractional Helly theorem for d-Leray complexes
- Borsuk-Ulam type theorem for the orthogonal group and orthogonal four-partitions
BibTeX
@misc{martinezsandoval2026pushed,
title = {{Pushed colorful polytopal KKMS Theorem and orthogonal star transversals}},
author = {Leonardo Martínez-Sandoval and Ariadna Olvera-Sampieri},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17157},
eprint = {2610.17157},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.17157},
}
RIS
TY - UNPB
TI - Pushed colorful polytopal KKMS Theorem and orthogonal star transversals
AU - Leonardo Martínez-Sandoval
AU - Ariadna Olvera-Sampieri
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.17157
UR - https://arxiv.org/abs/2610.17157
AB - A classical theorem of Kaiser and Rabinovich implies that if every subfamily of size at most ⌊log_2(d+1)⌋+1 of a finite family of compact connected sets in ℝ^d has a common axis-parallel hyperplane transversal, then the entire family has an orthogonal star transversal, i.e., a union of d hyperplanes, one perpendicular to each coordinate axis. We study colorful variants of this result. First, we use standard KKM machinery to establish a colorful analogue with d+1 color classes and a ⌊log_2(d+1)⌋+1 transversal hypothesis for rainbow subfamiles. Then we focus on reducing the required number of colors. To this end, we introduce the rainbow pushability π_r(P) of a polytope and we use it to state and prove few-color variants of the colorful Carathéodory theorem and the colorful polytopal KKMS theorem. Applying the latter to the d-dimensional cube, we show that ⌊log_2 d⌋+2 color classes suffice for our transversal problem, provided that every rainbow choice has a common axis-parallel hyperplane transversal. We also extend both colorful results to the setting of convex (n,D)-bodies and we show that three colors are needed for d≥ 2.
ER -