Beck–Fiala discrepancy conjecture

Let H\mathcal H be a hypergraph on a finite ground set XX, where every vertex has degree at most dd. Beck–Fiala's conjecture. There exists a function f:X{1,1}f:X\rightarrow\{-1,1\} such that for every eHe\in\mathcal H,

xef(x)Cd,\left|\sum_{x\in e}f(x)\right|\leqslant C\sqrt d,

where C>0C>0 is an absolute constant. The source describes this as the hypergraph-colouring companion to Komlós's conjecture and notes that Komlós's conjecture implies it; it is presented as open.

Sources & referencesView supporting material

Primary source

Julian Sahasrabudhe, “Probabilistic combinatorics at exponentially small scales”, arXiv:2512.15077 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.