Subcube Coverings of Random Spanning Subgraphs of the n-Cube

✍ Scribed by Karl Weber

• Publisher: John Wiley and Sons
• Year: 1985
• Tongue: English
• Weight: 896 KB
• Volume: 120
• Category: Article
• ISSN: 0025-584X
• DOI: 10.1002/mana.19851200128

✦ Synopsis

Let G(n, p )

denote the probability space consisting of all spanning subgraphs g of the n-cube En, and the probability is defined as

ERDOS and SPENCER investigated the connectedness of such random graphs for fixed probability p , O<p<l (cf. [l]). I n this paper we study coverings of the vertex set of g EG(n, p ) by subcubes of En 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 , by cliques.