Vector balancing in Lebesgue spaces. Issue 3 (26th August 2022)

• Record Type: Journal Article
• Authors: Reis, Victor; Rothvoss, Thomas
• Is Part Of: Random structures & algorithms. Volume 62:Issue 3(2023)
• Page Start: 667
• Page End: 688
• Publication Date: 2022-08-26
• Subjects: Beck‐Fiala conjecture -- discrepancy theory -- Komlós conjecture -- vector balancing; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21113
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: The Komlós conjecture suggests that for any vectors a 1, …, a n ∈ B 2 m $$ {\boldsymbol{a}}_1, \dots, {\boldsymbol{a}}_n\in {B}_2^m $$ there exist x 1, …, x n ∈ { − 1, 1 } $$ {x}_1, \dots, {x}_n\in \left\{-1, 1\right\} $$ so that ‖ ∑ i = 1 n x i a i ‖ ∞ ≤ O ( 1 ) $$ {\left\Vert {\sum}_{i=1}^n{x}_i{\boldsymbol{a}}_i\right\Vert}_{\infty}\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, \dots, {\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 $$ \delta >0 $$, a symmetric convex body K ⊆ ℝ n $$ K\subseteq {\mathbb{R}}^n $$ with Gaussian measure at least e − δ n $$ {e}^{-\delta n} $$ admits a partial coloring. Previously this was known only for a small enough δ $$ \delta $$ . Additionally, we show that a hereditary volume bound suffices to provide such Gaussian measure lower bounds.