The Minimization of Random Hypergraphs
share
We investigate the maximum-entropy model B_n,m,p for random n-vertex, m-edge multi-hypergraphs with expected edge size pn. We show that the expected number of inclusion-wise minimal edges of B_n,m,p undergoes a phase transition with respect to m. If m < 1/(1-p)^(1-p)n, the expectation is of order O(m), while for m > 1/(1-p)^(1-p)n, it is O(2^(H(α) + (1-α) ld p)n). Here, H denotes the binary entropy function and α = - (log_1-p m)/n. This implies that the maximum expected number of minimal edges over all m is O((1+p)^n). All asymptotics are with respect to n, for all upper bounds we have (almost) matching lower bounds. As a technical contribution, we establish the fact that the probability of a set of cardinality i being minimal after m i.i.d. maximum-entropy trials exhibits a sharp threshold behavior at i^* = n + log_1-p m, which is of independent interest. Our structural findings have algorithmic implications, for example, for computing the minimal hitting sets of a hypergraph as well as the profiling of relational databases.
READ FULL TEXT