Subcube Coverings of Random Spanning Subgraphs of the n ‐Cube

Let G(n, p) denote the probability space consisting of all spanning subgraphs g of the n ‐cube E n , and the probability is defined as P ( g ) = p M (1– p )   n 2   n –1– Mif g contains exactly M edges, 0 < M < n 2 n –1 . Erdös and Spencer investigated the connectedness of such random graphs for fixed probability p , 0 < p < 1 (cf. [1]). In this paper we study coverings of the vertex set of g ϵ G ( n , p ) by subcubes of E n being also subgraphs of g . Note the analogy between such coverings and coverings of the vertex set of spanning subgraphs of the complete graph K n by cliques.