Proving the Koml'os conjecture slowly
math.CO
Submitted: 2026-11-02
Updated: 2026-11-02
Comments: 30 pages, 5 figures
License: http://creativecommons.org/licenses/by/4.0/
The gist: The Komlós conjecture was a long-standing open problem in discrepancy theory until it was recently solved in a flurry of AI developments.
Terminology
Abstract
The Komlós conjecture was a long-standing open problem in discrepancy theory until it was recently solved in a flurry of AI developments. We give a motivated exposition of an elementary proof of the conjecture due to Karingula and Lovett, as well as a counterexample to the strong Komlós conjecture due to Kintali, aiming to introduce the ideas in a gentle and explained manner in order to ease the understanding of the proofs. We conclude with several problems which remain open.
Sources
- Online Beck--Fiala Down to Logarithmic Sparsity
- Vector Balancing in Polynomial Time
- The Komlos Conjecture Holds for Vector Colorings
- Discrepancy and Fisher information
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality