Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

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.

share|improve this answer
    
Thanks a lot! I will try to get in touch with him. –  Boris Bukh Oct 24 '09 at 14:46
    
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. –  Boris Bukh Nov 27 '09 at 10:13
add comment

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.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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