The continuous Beck-Fiala theorem is optimal. (English) Zbl 0847.05026
The authors consider the continuous version of the Beck-Fiala theorem. There, if the norm of every row in a matrix is at most 1, a bound \(\leq 1\) is given for the discrepancy. This is extended to the tight bound 1/2 if the dimension is at most 3 and if the dimension is \(n + 1\); an example shows that it cannot be decreased below \(n/(\sqrt {n} + 1)^2\).
Reviewer: P.Komjáth (Budapest)
MSC:
| 05B20 | Combinatorial aspects of matrices (incidence, Hadamard, etc.) |
| 15A45 | Miscellaneous inequalities involving matrices |
References:
| [1] | Akemann, C. A.; Anderson, J., Lyapunov theorems for operator algebras, Mem. Amer. Math. Soc., 94, 458 (1991) · Zbl 0769.46036 |
| [2] | Beck, J.; Fiala, T., Integer-making theorems, Discrete Appl. Math., 3, 1-8 (1981) · Zbl 0473.05046 |
| [3] | Lovasz, L.; Spencer, J.; Veztergombi, K., Discrepancy of set-systems and matrices, European J. Combin., 3, 151-159 (1986) · Zbl 0606.05001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
