Math Conjectures

Beck–Fiala Conjecture

OPENLandmarkConjectureProposed 1981 · Full conjecture

Canonical statement

There is a universal constant CC such that, for every finite set system S⊆2U\mathcal S\subseteq 2^U in which each element of UU belongs to at most tt sets, one can choose a coloring χ:U→{−1,+1}\chi:U\to\{-1,+1\} satisfying ∣∑x∈Aχ(x)∣≤Ct\left|\sum_{x\in A}\chi(x)\right|\le C\sqrt t for every A∈SA\in\mathcal S.
View source LaTeX
There is a universal constant \(C\) such that, for every finite set system \(\mathcal S\subseteq 2^U\) in which each element of \(U\) belongs to at most \(t\) sets, one can choose a coloring \(\chi:U\to\{-1,+1\}\) satisfying \(\left|\sum_{x\in A}\chi(x)\right|\le C\sqrt t\) for every \(A\in\mathcal S\).
COMB-DISC-015:[BeckFiala1981IntegerMaking][Banaszczyk1998Balancing][BansalJiang2025Decoupling][AltschulerTikhomirov2026OnlineBeckFiala]
CombinatoricsTheoretical computer science

Notes

A set system in which every element belongs to at most tt sets has discrepancy at most 2t−12t-1 by the original integer-making argument, and Beck and Fiala conjectured the dimension-free improvement O(t)O(\sqrt t) [BeckFiala1981IntegerMaking]. For a ground set of nn elements, Banaszczyk's vector-balancing theorem gives the classical O(tlog⁡n)O(\sqrt{t\log n}) bound [Banaszczyk1998Balancing].

Bansal and Jiang established the conjectured order when tt is at least about (log⁡n)2(\log n)^2 [BansalJiang2025Decoupling]. In July 2026, Altschuler and Tikhomirov pushed the offline validity range to t≥(log⁡n)1+o(1)t\ge(\log n)^{1+o(1)}, in work that also treats an online form [AltschulerTikhomirov2026OnlineBeckFiala]. Here nn is the number of ground-set elements; the sparser range remains open, and the online results do not by themselves prove the full offline conjecture for every tt and nn.

References (4)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.