On the discrepancy of random low degree set systems. Issue 3 (13th June 2020)

• Record Type: Journal Article
• Authors: Bansal, Nikhil; Meka, Raghu
• Is Part Of: Random structures & algorithms. Volume 57:Issue 3(2020)
• Page Start: 695
• Page End: 705
• Publication Date: 2020-06-13
• Subjects: Discrepancy -- random set system -- sparse; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20935
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : 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 when n ≤ m and an O (1) bound when n ≫ m t . 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 = m log O ( 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 ≤ m log O ( 1 ) m using LP duality and a careful counting argument.