The Minimization of Random Hypergraphs
Conference: European Symposium on Algorithms 2020
Speaker: Martin Schirneck
Abstract: In non-uniform hypergraphs there exists a phenomenon unknown to graphs: some edge may be contained in another, with edges even forming chains of inclusions. In many algorithmic applications we are only interested in the collection of inclusion-wise minimal edges, called the minimization of the hypergraph.
In the video we highlight our recent results on the minization of maximum-entropy hypergraphs with a prescribed number of edges and expected edge size. We give tigh bounds on the expected number of minimal edges and briefly touch on the tools used in the proofs. The most important technical contribution is an improvement of the Chernoff-Hoeffding theorem on the tail of the binomial distribution. In particular, we show that for a random variable \(X \sim \mathrm{Bin}(n,p)\) and any \(0 < x < p\), it holds that \(\mathrm{P}[X \le xn] = \Theta( 2^{-\mathrm{D}(x \,{\|}\, p) n}/\sqrt{n})\), where \(\mathrm{D}\) is the Kullback-Leibler divergence from information theory.
This is joined work with Thomas Bläsius and Tobias Friedrich.