Vector balancing in Lebesgue spaces

DOI10.1002/RSA.21113zbMATH Open1522.05482arXiv2007.05634WikidataQ114234625 ScholiaQ114234625MaRDI QIDQ6074880FDOQ6074880

Authors: Victor Reis, Thomas Rothvoß

Publication date: 19 October 2023

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

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.

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

Recommendations

zbMATH Keywords

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

Mathematics Subject Classification ID

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)

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)