Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 20 min ago
PreprintCC BY 4.0arXiv

Proving the Komlós conjecture slowly

  • Lawrence Hollom
Open at sourcePDFDOICite

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.

Related

  1. An elementary proof of the Komlós conjecture
    Sankeerth Rao Karingula, Shachar Lovett
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. The Komlós conjecture for complex discrepancy
    Nestor Guillen, Vladimir A. Kobzar
    arXivPreprintarXiv licenceFull textAnalysis & PDEsCombinatorics & discrete mathematicsarXiv
  3. An Exposition of the Õ(log1/4 n) Bound for the Komlós Problem
    Nikhil Bansal, Haotian Jiang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  4. Tighter bounds on Komlós discrepancy: existence and algorithmic results
    Emrullah Akbas, Suvrit Sra
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. A (log n)1/4 Bound for the Komlós Problem
    Eren Ercan
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{hollom2026proving,
  title = {{Proving the Komlós conjecture slowly}},
  author = {Lawrence Hollom},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.03427},
  eprint = {2611.03427},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.03427},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Proving the Komlós conjecture slowly
AU  - Lawrence Hollom
PY  - 2026
DA  - 2026/11/02
PB  - arXiv
DO  - 10.48550/arxiv.2611.03427
UR  - https://arxiv.org/abs/2611.03427
AB  - 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.
ER  -