Cores of random r-partite hypergraphs

We show that the threshold cr,k (in terms of the average degree of the graph) for appearance of a k-core in a random r-partite r-uniform hypergraph Gr,n,m is the same as for a random r-uniform hypergraph with cn/r edges without the r-partite restriction, where r,k⩾2. In both cases, the average degree is c. The case r,k=2 was analyzed in Botelho et al. (2007) [4], but the general case r⩾3, k⩾2 is still open. Besides the proof for the general case, we have also provided a simpler proof for the case r,k=2. This problem was provided without a proof (but with strong experimental evidence) in the analysis of the algorithm presented in Botelho et al. (2007) [2]. This algorithm constructs a family of minimal perfect hash functions based on random r-partite r-uniform hypergraphs with an empty k-core subgraph, for k⩾2. For an input key set S with m keys, the family of minimal perfect hash functions generated by the algorithm can be stored in O(m) bits, where the hidden constant is within a factor of two from the information theoretical lower bound.