The Phase Transition of Discrepancy in Random Hypergraphs

Source abstract

Abstract. Motivated by the Beck–Fiala conjecture, we study the discrepancy problem in two related models of random hypergraphs on [Formula: see text] vertices and [Formula: see text] edges. In the first model, each of the [Formula: see text] edges is constructed by placing each vertex into the edge independently with probability [Formula: see text], where [Formula: see text] is a parameter satisfying [Formula: see text] and [Formula: see text]. In the second model, each vertex independently chooses a subset of [Formula: see text] edge labels from [Formula: see text] uniformly at random. Edge [Formula: see text] is then defined to be exactly those vertices whose [Formula: see text]-subsets include label [Formula: see text]. In the sparse regime, i.e., when [Formula: see text], we show that with high probability a random hypergraph from either model has discrepancy at least [Formula: see text]. In the dense regime, i.e., when [Formula: see text], we show that with high probability a random hypergraph from either model has discrepancy at least [Formula: see text], where [Formula: see text]. Furthermore, we obtain nearly matching asymptotic upper bounds on the discrepancy. Specifically, we apply the partial coloring lemma of Lovett and Meka to show that, in the dense regime, with high probability the two random hypergraph models each have discrepancy [Formula: see text]. In fact, in a significant parameter range we can tighten our analysis to get an upper bound which matches our lower bound up to a constant factor. This result is algorithmic, and together with the work of Bansal and Meka [ On the discrepancy of random low degree set systems, in Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, pp. 2557–2564] characterizes how the discrepancy of each random hypergraph transitions from [Formula: see text] to [Formula: see text] as [Formula: see text] increases from [Formula: see text] to [Formula: see text].