Discrepancy of Random Set Systems: A Fourier-Analytic Approach

One of the prominent open problems in combinatorics is the discrepancy of set systems where each element lies in at most t sets. The Beck-Fiala conjecture suggests that the right bound is $O(\sqrt{t})$, but for three decades the only known bound not depending on the size of set system has been $O(t)$. Arguably we currently lack techniques for breaking that barrier. In this paper we introduce discrepancy bounds based on Fourier analysis and we demonstrate our method on random set systems. Under the assumption that the number of elements n is at least $O(m^2log(n))$, where $m$ is the number of sets, we show that a uniformly random set system will have a discrepancy bound of $1$ with high probability. This talk is based on joint work with Thomas Rothvoss.