3
$\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 a function f:X->{±1} such for every set S in H we have |sumx 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?

$\endgroup$
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$
  • $\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 '09 at 10:13
0
$\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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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