Induced subgraphs of hypercubes

Geir Agnarsson

Published 2011-12-13Version 1

Let $Q_k$ denote the $k$-dimensional hypercube on $2^k$ vertices. A vertex in a subgraph of $Q_k$ is {\em full} if its degree is $k$. We apply the Kruskal-Katona Theorem to compute the maximum number of full vertices an induced subgraph on $n\leq 2^k$ vertices of $Q_k$ can have, as a function of $k$ and $n$. This is then used to determine $\min(\max(|V(H_1)|, |V(H_2)|))$ where (i) $H_1$ and $H_2$ are induced subgraphs of $Q_k$, and (ii) together they cover all the edges of $Q_k$, that is $E(H_1)\cup E(H_2) = E(Q_k)$.