A note on the Beck-Fiala theorem (Q1375063): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: ``Integer-making'' theorems / rank | |||
Normal rank |
Latest revision as of 09:03, 28 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on the Beck-Fiala theorem |
scientific article |
Statements
A note on the Beck-Fiala theorem (English)
0 references
5 January 1998
0 references
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.
0 references
discrepancy
0 references
coloring
0 references
collection of subsets
0 references