Bläsius, Thomas ;
Friedrich, Tobias ;
Schirneck, Martin
The Minimization of Random Hypergraphs
Abstract
We investigate the maximumentropy model B_{n,m,p} for random nvertex, medge multihypergraphs with expected edge size pn. We show that the expected size of the minimization min(B_{n,m,p}), i.e., the number of inclusionwise minimal edges of B_{n,m,p}, undergoes a phase transition with respect to m. If m is at most 1/(1p)^{(1p)n}, then E[min(B_{n,m,p})] is of order Θ(m), while for m ≥ 1/(1p)^{(1p+ε)n} for any ε > 0, it is Θ(2^{(H(α) + (1α) log₂ p) n}/√n). Here, H denotes the binary entropy function and α =  (log_{1p} m)/n. The result implies that the maximum expected number of minimal edges over all m is Θ((1+p)ⁿ/√n). Our structural findings have algorithmic implications for minimizing an input hypergraph. This has applications in the profiling of relational databases as well as for the Orthogonal Vectors problem studied in finegrained complexity. We make several technical contributions that are of independent interest in probability. First, we improve the ChernoffHoeffding theorem on the tail of the binomial distribution. In detail, we show that for a binomial variable Y ∼ Bin(n,p) and any 0 < x < p, it holds that P[Y ≤ xn] = Θ(2^{D(x‖p) n}/√n), where D is the binary KullbackLeibler divergence between Bernoulli distributions. We give explicit upper and lower bounds on the constants hidden in the bigO notation that hold for all n. Secondly, we establish the fact that the probability of a set of cardinality i being minimal after m i.i.d. maximumentropy trials exhibits a sharp threshold behavior at i^* = n + log_{1p} m.
BibTeX  Entry
@InProceedings{blsius_et_al:LIPIcs:2020:12887,
author = {Thomas Bl{\"a}sius and Tobias Friedrich and Martin Schirneck},
title = {{The Minimization of Random Hypergraphs}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {21:121:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12887},
URN = {urn:nbn:de:0030drops128871},
doi = {10.4230/LIPIcs.ESA.2020.21},
annote = {Keywords: ChernoffHoeffding theorem, maximum entropy, maximization, minimization, phase transition, random hypergraphs}
}
26.08.2020
Keywords: 

ChernoffHoeffding theorem, maximum entropy, maximization, minimization, phase transition, random hypergraphs 
Seminar: 

28th Annual European Symposium on Algorithms (ESA 2020)

Issue date: 

2020 
Date of publication: 

26.08.2020 