2020-01-06
On the discrepancy of random low degree set systems
Publication
Publication
Motivated by the celebrated Beck-Fiala conjecture, we consider the random setting where there are n elements and m sets and each element lies in t randomly chosen sets. In this setting, Ezra and Lovett showed an O((t log t)1/2) discrepancy bound in the regime when n ≤ m and an O(1) bound when n ≫ mt. In this paper, we give a tight bound for the entire range of n and m, under a mild assumption that t = Ω(log log m)2. The result is based on two steps. First, applying the partial coloring method to the case when n = m logO(1) m and using the properties of the random set system we show that the overall discrepancy incurred is at most . Second, we reduce the general case to that of n ≤ m logO(1) m using LP duality and a careful counting argument.
| Additional Metadata | |
|---|---|
| doi.org/10.1137/1.9781611975482.157 | |
| Annual ACM-SIAM Symposium on Discrete Algorithms | |
| Organisation | Networks and Optimization |
|
Bansal, N., & Meka, R. (2020). On the discrepancy of random low degree set systems. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 2557–2564). doi:10.1137/1.9781611975482.157 |
|
| See Also |
|---|
