On the Beck-Fiala theorem (Q1817567): Difference between revisions

Let \(A=\{a_{1},a_{2},\ldots ,a_{n}\}\) be a finite set and let \({\mathcal T}= \{T_{1},T_{2},\ldots ,T_{k}\}\) be a collection of subsets of \(A\). A coloring \(c: A\rightarrow \{-1, 1\}\) of \(A\) induces a mapping \(f:{\mathcal T}\rightarrow Z\), where \(f(T_{j})=\sum_{a\in T_{j}} c(a)\). The discrepancy of \({\mathcal T}\), \(\text{disc}({\mathcal T})\), is defined by \(\text{disc}({\mathcal T})= \min_{c} \max_{T_{j}\in {\mathcal T}}|f(T_{j})|\), where the minimum is taken over all colorings of \(A\). In this paper the Beck-Fiala theorem [\textit{J. Beck} and \textit{T. Fiala}, Discrete Appl. Math. 3, 1--8 (1981; Zbl 0473.05046)] on discrepancy is slightly improved: if \({\mathcal T}\) has the property that each \(a_{i}\in A\) is contained in at most \(d\) sets \(T_{j}\in {\mathcal T}\) (\(d\) sufficiently large), then \(\text{disc}({\mathcal T})\leq 2d-4\).