Vector balancing in Lebesgue spaces. Issue 3 (26th August 2022) - Reis, Victor; Rothvoss, Thomas
Abstract: The Komlós conjecture suggests that for any vectors a 1, …, a n ∈ B 2 m $$ {\boldsymbol{a}}_1, …, {\boldsymbol{a}}_n\in {B}_2^m $$ there exist x 1, …, x n ∈ { − 1, 1 } $$ {x}_1, …, {x}_n\in \left\{-1, 1\right\} $$ so that ‖ ∑ i = 1 n x i a i ‖ ∞ ≤ O ( 1 ) $$ {\left\Vert {\sum}_{i=1}^nx_i{\boldsymbol{a}}_i\right\Vert}_{∞}\le O(1) $$ . It is a natural extension to ask what ℓ q $$ {\ell}_q $$ ‐norm bound to expect for a 1, …, a n ∈ B p m $$ {\boldsymbol{a}}_1, …, {\boldsymbol{a}}_n\in {B}_p^m $$ . We prove a tight partial coloring result for such vectors, implying a nearly tight full coloring bound. As a corollary, this implies a special case of Beck–Fiala's conjecture. We achieve this by showing that, for any δ > 0 $$ δ >0 $$, a symmetric convex body K ⊆ ℝ n $$ K\subseteq {\mathbb{R}}^n $$ with Gaussian measure at least e − δ n $$ {e}^{-δ n} $$ admits a partial coloring. Previously this was known only for a small enough δ $$ δ $$ . Additionally, we show that a hereditary volume bound suffices to provide such Gaussian measure lower bounds.