Return to Question

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?

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\colon 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?

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 a function f:X->{±1} such for every set S in H we have |sum_{x in S} f(x)|<=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≥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?

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?

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 a function f:X->{±1} such for every set S in H we have |sum_{x in S} f(x)|<=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≥3. The 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?

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 a function f:X->{±1} such for every set S in H we have |sum_{x in S} f(x)|<=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≥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?