A tantalizing conjecture in discrete mathematics is the one of Komlos, suggesting that for any vectors $mathbf{a}_1,ldots,mathbf{a}_n in B_2^m$ there exist signs $x_1, dots, x_n in { -1,1}$ so that $|sum_{i=1}^n x_imathbf{a}_i|_infty le O(1)$. It is a natural extension to ask what $ell_q$-norm bound to expect for $mathbf{a}_1,ldots,mathbf{a}_n in B_p^m$. We prove that, for $2 le p le q le infty$, such vectors admit fractional colorings $x_1, dots, x_n in [-1,1]$ with a linear number of $pm 1$ coordinates so that $|sum_{i=1}^n x_imathbf{a}_i|_q leq O(sqrt{min(p,log(2m/n))}) cdot n^{1/2-1/p+ 1/q}$, and that one can obtain a full coloring at the expense of another factor of $frac{1}{1/2 - 1/p + 1/q}$. In particular, for $p in (2,3]$ we can indeed find signs $mathbf{x} in { -1,1}^n$ with $|sum_{i=1}^n x_imathbf{a}_i|_infty le O(n^{1/2-1/p} cdot frac{1}{p-2})$. Our result generalizes Spencers theorem, for which $p = q = infty$, and is tight for $m = n$. Additionally, we prove that for any fixed constant $delta>0$, in a centrally symmetric body $K subseteq mathbb{R}^n$ with measure at least $e^{-delta n}$ one can find such a fractional coloring in polynomial time. Previously this was known only for a small enough constant -- indeed in this regime classical nonconstructive arguments do not apply and partial colorings of the form $mathbf{x} in { -1,0,1}^n$ do not necessarily exist.
Download