Is there an analogue of the Beck-Fiala theorem for linear or hereditary discrepancies of hypergraphs?
$\begingroup$
$\endgroup$
asked May 27, 2013 at 9:14
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If you take a subsystem, then the degree condition of the Beck-Fiala is still satisfied, so it is also trivially true for hereditary discrepancy. From Lovasz-Spencer-Vesztergombi, we know that the linear discrepancy can be bounded by twice the hereditary discrepancy, so almost the same bound applies for that as well.
