A note on the Beck-Fiala theorem
type: Item
instance of: scholarly article
title: A note on the Beck-Fiala theorem
zbMATH Open document ID: 0880.05002
DOI: 10.1007/BF01196138
author: D. Bednarchak
author: Martin Helm
published in: Combinatorica
publication date: 1998-01-05T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 1099685
zbMATH Keywords: discrepancy
zbMATH Keywords: coloring
zbMATH Keywords: collection of subsets
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
cites work: ``Integer-making'' theorems
Recommended article: On the Beck-Fiala theorem
Recommended article: An Improvement of the Beck–Fiala Theorem
Recommended article: A note on Bézout's theorem
Recommended article: On a theorem of Beck
Recommended article: A remark on the Beckman/Quarles theorem
Recommended article: On a Theorem of Beck and Putnam
Recommended article: Q5690075
Recommended article: Q4536879
Recommended article: A Note on Fubini's Theorem
Recommended article: A remark on the Segal-Becker theorem
description: scientific article; zbMATH DE number 1099685