Colorful Vector Balancing

2023/02/21 by Gergely Ambrus, Ambrus, Gergely, Rainie Bozzai +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Mathematical Approximation and Integration #Metric Geometry (math.MG) #Point processes and geometric inequalities #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.2302.10865

openalex publication_date 2023/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

We extend classical estimates for the vector balancing constant of ℝ^d equipped with the Euclidean and the maximum norms proved in the 1980's by showing that for p =2 and p=∞, given vector families V₁, …, V_n ⊂ B_p^d with 0 ∈ ∑_i=1ⁿ conv V_i, one may select vectors v_i ∈ V_i with ‖ v₁ + … + v_n ‖₂ ≤ √(d) for p=2, and ‖ v₁ + … + v_n ‖_∞ ≤ O(√(d)) for p = ∞. These bounds are sharp and asymptotically sharp, respectively, for n ≥ d. The proofs combine linear algebraic and probabilistic methods with a Gaussian random walk argument.

Related

• The Vector Balancing Constant for Zonotopes
• Discrepancy Minimization via a Self-Balancing Walk
• Approximate Carathéodory bounds via Discrepancy Theory
• Vector Balancing in Lebesgue Spaces
• Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem