Discrepancy in random hypergraph models
share
We study hypergraph discrepancy in two closely related random models of hypergraphs on n vertices and m hyperedges. The first model, H_1, is when every vertex is present in exactly t randomly chosen hyperedges. The premise of this is closely tied to, and motivated by the Beck-Fiala conjecture. The second, perhaps more natural model, H_2, is when the entries of the m × n incidence matrix is sampled in an i.i.d. fashion, each with probability p. We prove the following: 1. In H_1, when ^10n ≪ t ≪√(n), and m = n, we show that the discrepancy of the hypergraph is almost surely at most O(√(t)). This improves upon a result of Ezra and Lovett for this range of parameters. 2. In H_2, when p= 1/2, and n = Ω(m m), we show that the discrepancy is almost surely at most 1. This answers an open problem of Hoberg and Rothvoss.
READ FULL TEXT