On the Beck-Fiala Conjecture for Random Set Systems

Combinatorics Seminar
Friday, December 4, 2015 - 3:00pm
1 hour (actually 50 minutes)
Skiles 005
Georgia Tech

Joint work with Shachar Lovett.

    Motivated by the Beck-Fiala conjecture, we study discrepancy bounds for random sparse set systems. Concretely, these are set systems (X,\Sigma), where each element x \in X lies in t randomly selected sets of \Sigma, where t \le |X| is an integer parameter. We provide new discrepancy bounds in this case. Specifically, we show that when |\Sigma| \ge |X| the hereditary discrepancy of (X,\Sigma) is with high probability O(\sqrt{t \log t}), matching the Beck-Fiala conjecture upto a \sqrt{\log{t}} factor. Our analysis combines the Lov{\'a}sz Local Lemma with a new argument based on partial matchings.