Vector balancing in Lebesgue spaces

DOI10.1002/RSA.21113MaRDI QIDQ6074880zbMATH OpenWikidataFDO

Publication date 19 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.05634

discrepancy theory vector balancing Beck-Fiala conjecture Komlós conjecture

Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Inequalities and extremum problems involving convexity in convex geometry (52A40) Extremal set theory (05D05) Ramsey theory (05D10)

Abstract: A tantalizing conjecture in discrete mathematics is the one of Koml'os, suggesting that for any vectors

m a t h b f a_{1}, l d o t s, m a t h b f a_{n} i n B_{2}^{m}

there exist signs

x_{1}, d o t s, x_{n} i n - 1, 1

so that

| s u m_{i = 1}^{n} x_{i} m a t h b f a_{i} |_{i} n f t y l e O (1)

. It is a natural extension to ask what

e l l_{q}

-norm bound to expect for

m a t h b f a_{1}, l d o t s, m a t h b f a_{n} i n B_{p}^{m}

. We prove that, for

2 l e p l e q l e i n f t y

, such vectors admit fractional colorings

x_{1}, d o t s, x_{n} i n [- 1, 1]

with a linear number of

p m 1

coordinates so that

| s u m_{i = 1}^{n} x_{i} m a t h b f a_{i} |_{q} l e q O (s q r t m i n (p, l o g (2 m / n))) c d o t n^{1 / 2 - 1 / p + 1 / q}

, and that one can obtain a full coloring at the expense of another factor of

f r a c 1 1 / 2 - 1 / p + 1 / q

. In particular, for

p i n (2, 3]

we can indeed find signs

m a t h b f x i n {- 1, 1}^{n}

with

| s u m_{i = 1}^{n} x_{i} m a t h b f a_{i} |_{i} n f t y l e O (n^{1 / 2 - 1 / p} c d o t f r a c 1 p - 2)

. Our result generalizes Spencer's theorem, for which

p = q = i n f t y

, and is tight for

m = n

. Additionally, we prove that for any fixed constant

d e l t a > 0

, in a centrally symmetric body

K s u b s e t e q m a t h b b R^{n}

with measure at least

e^{- d e l t a 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

m a t h b f x i n {- 1, 0, 1}^{n}

do not necessarily exist.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Vector balancing in Lebesgue spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074880)