Colorful Vector Balancing

Publication date 21 February 2023

Abstract: We extend classical estimates for the vector balancing constant of

m a t h b b R^{d}

equipped with the Euclidean and the maximum norms proved in the 1980's by showing that for

p = 2

and

p = i n f t y

, given vector families

V_{1}, l d o t s, V_{n} s u b s e t B_{p}^{d}

with

0 i n s u m_{i = 1}^{n} m a t h r m c o n v, V_{i}

, one may select vectors

v_{i} i n V_{i}

with [ | v_1 + ldots + v_n |_2 leq sqrt{d} ] for

p = 2

, and [ | v_1 + ldots + v_n |_infty leq O(sqrt{d}) ] for

p = i n f t y

. These bounds are sharp and asymptotically sharp, respectively, for

n g e q d

, and they significantly strengthen the estimate of B'ar'any and Grinberg for general norms on

m a t h b b R^{d}

. The proofs combine linear algebraic and probabilistic methods with a Gaussian random walk argument.

This page was built for publication: Colorful Vector Balancing