Back to Search Start Over

An improvement of the Beck-Fiala theorem

Authors :
Bukh, Boris
Publication Year :
2013

Abstract

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.<br />Comment: 18 pages

Subjects

Subjects :
Mathematics - Combinatorics
05D05, 11K38, 05C15
G.2.2

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1306.6081
Document Type :
Working Paper

Tools

Authors Abstract Subjects Details