Discrepancy in random hypergraph models

MaRDI QIDQ6309197zbMATH OpenFDO

Authors Aditya Potukuchi

Publication date 4 November 2018

Abstract: We study hypergraph discrepancy in two closely related random models of hypergraphs on $n$ vertices and $m$ hyperedges. The first model, $mathcal{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, $mathcal{H}_2$, is when the entries of the $mimesn$ incidence matrix is sampled in an i.i.d. fashion, each with probability $p$. We prove the following: 1. In $mathcal{H}_1$, when $lo{g}^{10}nlltllsqrtn$, and $m=n$, we show that the discrepancy of the hypergraph is almost surely at most $O(sqrtt)$. This improves upon a result of Ezra and Lovett for this range of parameters. 2. In $mathcal{H}_2$, when $p=frac12$, and $n=Omega(mlogm)$, we show that the discrepancy is almost surely at most $1$. This answers an open problem of Hoberg and Rothvoss.

This page was built for publication: Discrepancy in random hypergraph models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6309197)