A note on the Beck-Fiala theorem (Q1375063): Difference between revisions

Let \(A=\{a_{1},a_{2},\ldots ,a_{n}\}\) and \(c:A\rightarrow \{-1,1\}\) be a coloring of \(A\). For every collection of subsets of \(A\), \({\mathcal T} =\{T_{1},\ldots ,T_{k}\}\), the coloring \(c\) induces a mapping \(f:{\mathcal T} \rightarrow\mathbb{Z}\), where \(f(T_{j})=\sum_{a\in T_{j}}c(a)\). The discrepancy of \({\mathcal T}\), \(\operatorname{disc}({\mathcal T})\), is defined by \(\operatorname{disc}({\mathcal T})=\min_{c} \max_{T_{j}\in {\mathcal T}}|f(T_{j})|\) where the minimum is taken over all colorings of \(A\). It is proved that if \({\mathcal T}\) has the property that each \(a_{i}\in A\) is contained in at most \(d\geq 3\) sets \(T_{j}\in {\mathcal T}\), then \(\operatorname{disc}({\mathcal T})\leq 2d-3\). This is a slight improvement of a well-known theorem of Beck and Fiala.