2012/04/10 by Rink, Michael
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #G.1.6 #G.2.2
paper · doi:10.48550/arxiv.1204.2131
We study thresholds for the appearance of a 2-core in random hypergraphs that are a mixture of a constant number of random uniform hypergraphs each with a linear number of edges but with different edge sizes. For the case of two overlapping hypergraphs we give a solution for the optimal (expected) number of edges of each size such that the 2-core threshold for the resulting mixed hypergraph is maximized. We show that for adequate edge sizes this threshold exceeds the maximum 2-core threshold for any random uniform hypergraph, which can be used to improve the space utilization of several data structures that rely on this parameter.