Skip to content
DraconiticResearch
Search Sources API
186,541 studies31 sourcesUpdated 2 min ago
PreprintarXiv licencearXiv

An Exposition of the Õ(log1/4 n) Bound for the Komlós Problem

  • Nikhil Bansal
  • Haotian Jiang
Open at sourcePDFDOICite

Abstract

A conjecture of Komlós states that the combinatorial discrepancy of any matrix A∈ℝm× n whose columns have Euclidean norm at most one is bounded by a universal constant. We prove that the combinatorial discrepancy of every such matrix is at most O((log n)1/4(loglog n)7/4). This is the first asymptotic improvement over the O(√(log n)) bound established by Banaszczyk [Banaszczyk, Random Struct.\ Algorithms, 1998], and it refutes a conjecture of Hajela [Hajela, European J.\ Combin., 1988] that a lower bound of order Ω(√(log n)) should hold.

Related

  1. A (log n)1/4 Bound for the Komlós Problem
    Eren Ercan
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. A short proof of a quadratic lower bound on the border determinantal complexity of x1n+⋯+xnn over ℂ: A simple human exposition
    Karthik Sheshadri
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  3. An explicit lower bound for the unit distance problem
    Will Sawin
    arXiv (Cornell University)PreprintLicence not statedFull text14 citedCombinatorics & discrete mathematicsOpenAlex
  4. A Uniform Bound on Optimal Strategy Length in Water Transport Problem
    Tianyi Tao, Bohan Yang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. A near-quadratic lower bound for the Brown--Erdős--Sós (9,6)-problem
    Xiangliang Kong, Chong Shangguan, Xin Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{bansal2026exposition,
  title = {{An Exposition of the $\widetildeO(\log^1/4 n)$ Bound for the Komlós Problem}},
  author = {Nikhil Bansal and Haotian Jiang},
  howpublished = {arXiv},
  year = {2026},
  month = aug,
  doi = {10.48550/arxiv.2608.28452},
  eprint = {2608.28452},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.28452},
}
RIS
TY  - UNPB
TI  - An Exposition of the Õ(log^1/4 n) Bound for the Komlós Problem
AU  - Nikhil Bansal
AU  - Haotian Jiang
PY  - 2026
DA  - 2026/08/28
PB  - arXiv
DO  - 10.48550/arxiv.2608.28452
UR  - https://arxiv.org/abs/2608.28452
AB  - A conjecture of Komlós states that the combinatorial discrepancy of any matrix A∈ℝ^m× n whose columns have Euclidean norm at most one is bounded by a universal constant. We prove that the combinatorial discrepancy of every such matrix is at most O((log n)^1/4(loglog n)^7/4). This is the first asymptotic improvement over the O(√(log n)) bound established by Banaszczyk [Banaszczyk, Random Struct.\ Algorithms, 1998], and it refutes a conjecture of Hajela [Hajela, European J.\ Combin., 1988] that a lower bound of order Ω(√(log n)) should hold.
ER  -