pith. sign in

arxiv: 1811.01491 · v1 · pith:UM5B37ITnew · submitted 2018-11-05 · 🧮 math.CO · cs.DM

Discrepancy in random hypergraph models

classification 🧮 math.CO cs.DM
keywords discrepancymathcalwhenhypergraphalmostcloselyhyperedgesmodel
0
0 comments X
read the original 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 $m \times n$ incidence matrix is sampled in an i.i.d. fashion, each with probability $p$. We prove the following: 1. In $\mathcal{H}_1$, when $\log^{10}n \ll t \ll \sqrt{n}$, and $m = n$, we show that the discrepancy of the hypergraph is almost surely at most $O(\sqrt{t})$. This improves upon a result of Ezra and Lovett for this range of parameters. 2. In $\mathcal{H}_2$, when $p= \frac{1}{2}$, and $n = \Omega(m \log m)$, we show that the discrepancy is almost surely at most $1$. This answers an open problem of Hoberg and Rothvoss.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.