2020/07/10 by Reis, Victor, Rothvoss, Thomas
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2007.05634
A tantalizing conjecture in discrete mathematics is the one of Komlós, suggesting that for any vectors a1,…,an ∈ B2m there exist signs x1, …, xn ∈ \ -1,1\ so that ‖∑i=1n xiai‖_∞ ≤ O(1). It is a natural extension to ask what ℓq-norm bound to expect for a1,…,an ∈ Bpm. We prove that, for 2 ≤ p ≤ q ≤ ∞, such vectors admit fractional colorings x1, …, xn ∈ [-1,1] with a linear number of ± 1 coordinates so that ‖∑i=1n xiai‖q ≤ O(√(min(p,log(2m/n)))) ⋅ n1/2-1/p+ 1/q, and that one can obtain a full coloring at the expense of another factor of (1)/(1/2 - 1/p + 1/q). In particular, for p ∈ (2,3] we can indeed find signs x ∈ \ -1,1\n with ‖∑i=1n xiai‖_∞ ≤ O(n1/2-1/p ⋅ (1)/(p-2)). Our result generalizes Spencer's theorem, for which p = q = ∞, and is tight for m = n. Additionally, we prove that for any fixed constant δ>0, in a centrally symmetric body K ⊆ ℝn with measure at least e-δ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 x ∈ \ -1,0,1\n do not necessarily exist.