On the discrepancy of random matrices with many columns. Issue 1 (26th March 2020) - Franks, Cole
Abstract : Motivated by the Komlós conjecture in combinatorial discrepancy, we study the discrepancy of random matrices with m rows and n independent columns drawn from a bounded lattice random variable. We prove that for n at least polynomial in m, with high probability the ℓ ∞ ‐discrepancy is at most twice the ℓ ∞ ‐covering radius of the integer span of the support of the random variable. Applying this result to random t ‐sparse matrices, that is, uniformly random matrices with t ones and m − t zeroes in each column, we show that the ℓ ∞ ‐discrepancy is at most 2 with probability 1 − 3 exp ( − Ω ( n / m ) ) for n = Ω ( m 3 log 2 m ) . This improves on a bound proved by Ezra and Lovett showing the same bound for n at least m t .