Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 44 min ago
PreprintarXiv licencearXiv

Vector Balancing via Directional Total Variation

  • Shengtao Guo1
  • Ethan X. Fang1
  • Junwei Lu1
  1. 1Department of Biostatistics , Harvard T.H. Chan School of Public Health
Open at sourcePDFDOICite

Abstract

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

Related

  1. An optimal constant for vector balancing with permutations
    Jonathan Niles-Weed, Shay Sadovsky, Jacob Shkrob
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsGeometry & topologyarXiv
  2. Subgaussian Vector Balancing by an Ising Model
    Heng Guo, Daniel A. Spielman, Xinyuan Zhang
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  3. Gaussian and non-Gaussian limits for the total edge-length of random directional nearest-neighbour graphs
    Nicholas Georgiou, Qasem M. Tawhari, Andrew Wade
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  4. Vector Balancing in Polynomial Time
    Shengtao Guo, Ethan X. Fang, Junwei Lu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Degrees and directional defects of embedded algebraic vector bundles
    Leonardo Lanciano
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{guo2026vector,
  title = {{Vector Balancing via Directional Total Variation}},
  author = {Shengtao Guo and Ethan X. Fang and Junwei Lu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.11189},
  eprint = {2609.11189},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.11189},
}
RIS
TY  - UNPB
TI  - Vector Balancing via Directional Total Variation
AU  - Shengtao Guo
AU  - Ethan X. Fang
AU  - Junwei Lu
PY  - 2026
DA  - 2026/09/10
PB  - arXiv
DO  - 10.48550/arxiv.2609.11189
UR  - https://arxiv.org/abs/2609.11189
AB  - Our main result is a 3√(2π) bound for the Komlós signing problem: every finite family of real vectors of Euclidean norm at most one admits a signed sum of ℓ_∞-norm less than this constant, independently of the dimension and the family size. For any κ≥0, if a bounded open convex set supports a probability density with directional total variation at most κ in every unit direction, then its open-set Banaszczyk transform supports another such density with the same κ, provided the translation vector v satisfies κ|v|_2≤1/3. As a consequence, every finite set system in which each element belongs to at most t sets, where t≥1 is an integer, admits a two-coloring whose imbalance in each set is less than 3√(2πt). This gives the square-root dependence predicted by the Beck-Fiala conjecture. The proof was discovered by the Odin Automatic AI Research Agent.
SN  - 2331-8422
ER  -