Colorful Vector Balancing

We extend classical estimates for the vector balancing constant of ${\mathbb{R}}^d$ equipped with the Euclidean and the maximum norms proved in the 1980’s by showing that for $p=2$ and $p=\mathrm{\infty }$, given vector families $V_1,\dots ,V_n\subset B_p^d$ with $0\in {\sum }_{i=1}^n\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}{V}_i$, one may select vectors $v_i\in V_i$ with $\mathrm{\parallel }{v}_1+\dots +v_n{\mathrm{\parallel }}_2\le \sqrt{d}$ for $p=2$, and $\mathrm{\parallel }{v}_1+\dots +v_n{\mathrm{\parallel }}_{\mathrm{\infty }}\le O(\sqrt{d})$ for $p=\mathrm{\infty }$. These bounds are sharp and asymptotically sharp, respectively, for $n\ge d$. The proofs combine linear algebraic and probabilistic methods with a Gaussian random walk argument.