Beck–Fiala theorem and conjecture

Discrepancy of bounded-degree set systems. Given sets $S_1, \dots, S_m \subseteq [n]$ such that every element of $[n]$ belongs to at most $t$ of the sets (the system has degree at most $t$), one seeks a colouring $\chi \colon [n] \to \{-1, +1\}$ making every set as balanced as possible, i.e. minimizing the discrepancy $\max_i \left|\sum_{j \in S_i} \chi(j)\right|$.

The Beck–Fiala theorem (1981) states that every set system of degree at most $t \ge 1$ has discrepancy at most $2t - 1$. The Beck–Fiala conjecture asserts that the truth is much stronger: the discrepancy of a degree-$t$ system is $O(\sqrt{t})$, with a constant independent of $n$, $m$ and $t$.

Despite considerable attention the bound $2t - 1$ has been improved only slightly: Bukh (2016) proved a bound of the form $2t - \log^* t$ (where $\log^*$ is the iterated logarithm), and Banaszczyk's vector balancing theorem yields $O(\sqrt{t \log n})$. The Komlós conjecture (see KomlosConjecture.lean) would imply the Beck–Fiala conjecture, since scaling the incidence vectors of a degree-$t$ system by $1/\sqrt{t}$ produces vectors of Euclidean norm at most $1$.

References:

• Wikipedia
• J. Beck and T. Fiala, "Integer-making" theorems, Discrete Applied Mathematics 3 (1981), 1–8
• B. Bukh, An improvement of the Beck–Fiala theorem, Combinatorics, Probability and Computing 25 (2016), 380–398
• W. Banaszczyk, Balancing vectors and Gaussian measures of n-dimensional convex bodies, Random Structures & Algorithms 12 (1998), 351–360

theorem BeckFiala.beck_fiala_theorem (n m t : ℕ) (ht : 1 ≤ t) (S : Fin m → Finset (Fin n)) (hdeg : ∀ (j : Fin n), {i : Fin m | j ∈ S i}.card ≤ t) : ∃ (χ : Fin n → ℝ), (∀ (j : Fin n), χ j = 1 ∨ χ j = -1) ∧ ∀ (i : Fin m), |∑ j ∈ S i, χ j| ≤ 2 * ↑t - 1

The Beck–Fiala theorem

If $S_1, \dots, S_m \subseteq [n]$ is a set system of degree at most $t$, i.e. every $j \in [n]$ lies in at most $t$ of the sets, and $t \ge 1$, then there is a colouring $\chi \colon [n] \to \{-1, +1\}$ with $\left|\sum_{j \in S_i} \chi(j)\right| \le 2t - 1$ for every $i$.

The hypothesis $t \ge 1$ is necessary: a system of degree $0$ consists of empty sets only, whose discrepancy is $0 > 2 \cdot 0 - 1$.

[J. Beck and T. Fiala, "Integer-making" theorems, Discrete Applied Mathematics 3 (1981), 1–8.]

theorem BeckFiala.beck_fiala_conjecture : ∃ (C : ℝ), 0 < C ∧ ∀ (n m t : ℕ) (S : Fin m → Finset (Fin n)), (∀ (j : Fin n), {i : Fin m | j ∈ S i}.card ≤ t) → ∃ (χ : Fin n → ℝ), (∀ (j : Fin n), χ j = 1 ∨ χ j = -1) ∧ ∀ (i : Fin m), |∑ j ∈ S i, χ j| ≤ C * √↑t

The Beck–Fiala conjecture

There exists a universal constant $C > 0$ such that every set system $S_1, \dots, S_m \subseteq [n]$ of degree at most $t$ admits a colouring $\chi \colon [n] \to \{-1, +1\}$ with $\left|\sum_{j \in S_i} \chi(j)\right| \le C \sqrt{t}$ for every $i$.

theorem BeckFiala.beck_fiala_conjecture.variants.no_sets (n t : ℕ) (S : Fin 0 → Finset (Fin n)) (_hdeg : ∀ (j : Fin n), {i : Fin 0 | j ∈ S i}.card ≤ t) : ∃ (χ : Fin n → ℝ), (∀ (j : Fin n), χ j = 1 ∨ χ j = -1) ∧ ∀ (i : Fin 0), |∑ j ∈ S i, χ j| ≤ √↑t

Sanity check: a system with no sets at all ($m = 0$) admits any colouring vacuously; in particular the all-ones colouring satisfies every discrepancy bound.