Leírás
The vector balancing constant of two symmetric convex bodies
K,Q is the minimum r ≥ 0 so that any number of vectors from K can be
balanced into an r-scaling of Q. A question raised by Schechtman is
whether for any d-dimensional zonotope K, one has vb(K , K )
=O(sqrt(d)) . Intuitively, this asks whether a natural geometric
generalization of Spencer’s Theorem (for which K is the cube ) holds.
We prove that for any d-dimensional zonotope K one has vb(K , K )
=O(sqrt(d) log log log d ). Our main technical contribution is a tight
lower bound on the Gaussian measure of any section of a normalized
zonotope, generalizing Vaaler’s Theorem for cubes. We also prove that
for two different normalized zonotopes K and Q one has
vb(K,Q)=O(sqrt(dlogd)). All of the bounds are constructive and the
corresponding colorings can be computed in polynomial time.