The Minimization of Random Hypergraphs

DOI10.4230/LIPICS.ESA.2020.21arXiv1910.00308MaRDI QIDQ6326314FDOQ6326314

Authors: Thomas Bläsius, Tobias Friedrich, Martin Schirneck 

Publication date: 1 October 2019

Abstract: We investigate the maximum-entropy model $mathcal{B}_{n,m,p}$ for random $n$-vertex, $m$-edge multi-hypergraphs with expected edge size $pn$. We show that the expected size of the minimization of $mathcal{B}_{n,m,p}$, i.e., the number of its inclusion-wise minimal edges, undergoes a phase transition with respect to $m$. If $m$ is at most $1/(1-p{)}^{(1-p)n}$, then the minimization is of size $Theta(m)$. Beyond that point, for $alpha$ such that $m=1/(1-p{)}^{alphan}$ and $mathrmH$ being the entropy function, it is $Theta(1)cdotmin!left(1,,frac1(alpha,-,(1-p))sqrt(1,-,alpha)night)cdot{2}^{(mathrmH(alpha)+(1-alpha)lo{g}_{2}p)n}.$ This implies that the maximum expected size over all $m$ is $Theta((1+p{)}^n/sqrtn)$. Our structural findings have algorithmic implications for minimizing an input hypergraph, which in turn has applications in the profiling of relational databases as well as for the Orthogonal Vectors problem studied in fine-grained complexity. The main technical tool is an improvement of the Chernoff--Hoeffding inequality, which we make tight up to constant factors. We show that for a binomial variable $XsimmathrmBin(n,p)$ and real number $0<xlep$, it holds that $mathrmP[Xlexn]=Theta(1)cdotmin!left(1,,frac1(p-x)sqrtxnight)cdot{2}^{-!mathrmD(x,|,p)n}$, where $mathrmD$ denotes the Kullback--Leibler divergence between Bernoulli distributions. The result remains true if $x$ depends on $n$ as long as it is bounded away from $0$.

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

This page was built for publication: The Minimization of Random Hypergraphs

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