Skip to main content

Helm's improvement to Beck-Fiala theorem

Beck-Fiala theorem states that if $X$ is a finite set and $H$ is any family of subsets of $X$, in which every vertex occurs in at most $d$ sets of $H$, then there is a function $f:X\to\{1,-1\}$ such that for every set $S$ in $H$ we have $|\sum_{x\in S} f(x)|\le 2d-2$. In combinatorics parlance, one formulates this as "every hypergraph of maximal degree $d$ has discrepancy at most $2d-2$". The theorem is striking since the bound on discrepancy depends only on $d$, but not on the sizes of $X$ and $H$.

There were two papers that improve the bound of $2d-2$. The first is due to Bednarchak and Helm, which replaces $2d-2$ by $2d-3$ for $d\ge 3$. Their argument is short and sweet. The later improvement is due to Helm to $2d-4$. However, I have been unable to follow the paper. I also tried to contact the author, but I could not locate him. Has anyone been able to follow the paper, or at least understood the algorithm to find f well enough to explain it in pseudo-code?

Boris Bukh
  • 7.8k
  • 1
  • 36
  • 71