Covering the Edges of a Random Hypergraph by Cliques

Abstract

We determine the order of magnitude of the minimum clique cover of the edges of a binomial, r-uniform, random hypergraph G(r)(n, p), p fixed. In doing so, we combine the ideas from the proofs of the graph case (r = 2) in Frieze and Reed [Covering the edges of a random graph by cliques, Combinatorica 15 (1995) 489–497] and Guo, Patten, Warnke [Prague dimension of random graphs, manuscript submitted for publication].

Keywords

• r-uniform random hypergraph
• clique covering
• 05c65
• 05c80
• 05c62
• 05c69
• 05c70
• 05c75