file.pdf (228.21 kB)
Download file

An improvement of the Beck-Fiala theorem

Download (228.21 kB)
journal contribution
posted on 2015-03-01, 00:00 authored by Boris Bukh

In 1981 Beck and Fiala proved an upper bound for the discrepancy of a set system of degree d that is independent of the size of the ground set. In the intervening years the bound has been decreased from 2d − 2 to 2d − 4. We improve the bound to 2d − log∗ d

History

Date

2015-03-01

Usage metrics

Licence

Exports