Mathematics > Combinatorics

Title:Vector Balancing via Directional Total Variation

View PDF HTML (experimental) Abstract:Our main result is a $3\sqrt{2\pi}$ bound for the Komlós signing problem: every finite family of real vectors of Euclidean norm at most one admits a signed sum of $\ell_\infty$-norm less than this constant, independently of the dimension and the family size. For any $\kappa\ge0$, if a bounded open convex set supports a probability density with directional total variation at most $\kappa$ in every unit direction, then its open-set Banaszczyk transform supports another such density with the same $\kappa$, provided the translation vector $v$ satisfies $\kappa|v|_2\le1/3$. As a consequence, every finite set system in which each element belongs to at most $t$ sets, where $t\ge1$ is an integer, admits a two-coloring whose imbalance in each set is less than $3\sqrt{2\pi t}$. This gives the square-root dependence predicted by the Beck-Fiala conjecture. The proof was discovered by the Odin Automatic AI Research Agent.

Current browse context:

Bibliographic and Citation Tools

Code, Data and Media Associated with this Article

Demos

Recommenders and Search Tools

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.