Almost partitioning the hypercube into copies of a graph

Abstract

Let $H$ be an induced subgraph of the hypercube $Q_k$, for some $k$. We show that for some $c=c(H)$, the vertices of $Q_n$ can be partitioned into induced copies of $H$ and a remainder of at most $O(n^c)$ vertices. We also show that the error term cannot be replaced by anything smaller than $\log n$.

13 pages, 1 figure

References in corpus (2)

• Decomposing the vertex set of a hypercube into isomorphic subgraphs
• Almost tiling of the Boolean lattice with copies of a poset