On the discrepancy of random low degree set systems
Random Structures & Algorithms , Volume 57 - Issue 3 p. 695- 705
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((tlogt)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 O(√t) 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=mlogO(1)m and using the properties of the random set system we show that the overall discrepancy incurred is at most O(√t). Second, we reduce the general case to that of n≤mlogO(1)m using LP duality and a careful counting argument.
|Random Structures & Algorithms|
|Continuous Methods in Discrete Optimization|
|Organisation||Networks and Optimization|
Bansal, N, & Meka, R. (2020). On the discrepancy of random low degree set systems. Random Structures & Algorithms, 57(3), 695–705. doi:10.1002/rsa.20935