An Exposition of the $\widetilde{O}(\log^{1/4} n)$ Bound for the Komlós Problem
A conjecture of Komlós states that the combinatorial discrepancy of any matrix $A\in\mathbb R^{m\times 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}(\log\log n)^{7/4})$. This is the first asymptotic improvement over the $O(\sqrt{\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 $Ω(\sqrt{\log n})$ should hold.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.28452
curl -X POST /api/v1/records/arxiv/2608.28452/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.28452/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'