5
$\begingroup$

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?

$\endgroup$

2 Answers 2

2
$\begingroup$

The author Martin Helm seems nowadays to be a faculty member in financial engineering at Baruch College, see this http://www.baruch.cuny.edu/math/mfe_faculty.html Hope this helps.

$\endgroup$
1
  • $\begingroup$ I tried to get in touch with him, but he does not currently teach in the department, and there are no replies to the e-mails. So, my question still stands. $\endgroup$
    – Boris Bukh
    Nov 27, 2009 at 10:13
2
$\begingroup$

I still do not understand Helm's paper, and in particular what his algorithm for finding a coloring is. I found an argument that improves on Helm's result. Some of the ideas in the new argument are similar to what Helm seems to have used. The paper is available at http://arxiv.org/abs/1306.6081. (Sorry for answering my own question with a reference to my own paper.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.