Abstract | ||
---|---|---|
Lovasz, Spencer and Vesztergombi proved that the linear discrepancy of a hypergraph H is bounded above by the hereditary discrepancy of H, and conjectured a sharper bound that involves the number of vertices in H. In this paper we give a short proof of this conjecture for hypergraphs of hereditary discrepancy 1. For hypergraphs of higher hereditary discrepancy we give some partial results and propose a sharpening of the conjecture. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1007/s00493-005-0003-9 | Combinatorica |
Field | DocType | Volume |
Discrete mathematics,Mathematics | Journal | 25 |
Issue | ISSN | Citations |
1 | 1439-6912 | 2 |
PageRank | References | Authors |
0.46 | 5 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tom Bohman | 1 | 250 | 33.01 |
Ron Holzman | 2 | 287 | 43.78 |