How many connected induced subgraphs does a hypercube of dimension n have?

Question

Let $Q_n$ be the graph formed from the vertices and edges of an $n$-dimensional hypercube. How many connected induced subgraphs does it have?

Two connected induced subgraphs are the same if and only if they have the exact same vertices.

Answer 1

An exact count is tough to obtain. You can find the first few values in OEIS sequence A290758.

For an asymptotic estimate, let's pick an induced subgraph of $Q_n$ uniformly at random and consider its isolated vertices. There are $2^n$ vertices in the graph. Each one of them is an isolated vertex with probality $\frac1{2^{n+1}}$: for this to happen, it must appear in the subgraph, and none of its $n$ neighbors can appear. So the expected number of isolated vertices is $2^n \cdot \frac1{2^{n+1}} = \frac12$.

For large $n$, these isolated vertices appear close to independently. So, we can approximate the number of isolated vertices by a Poisson variable with mean $\frac12$. In particular, the probability is that there are no isolated vertices should tend to $e^{-1/2}$ as $n \to \infty$.

Connected components that are bigger than an isolated vertex will be much more rare. Consider for example the $2$-vertex connected components: there are $n 2^{n-1}$ possible components like this, which is not too much bigger than the number of vertices. But the probability that one of them is a connected component of the induced subgraph is much smaller: it is $\frac1{2^{2n}}$. The expected number is $\frac{n}{2^{n+1}}$, which is tiny. As we add more vertices, this probability will fall even more quickly.

So, we can estimate the number of connected induced subgraphs of $Q_n$ as $e^{-1/2} \cdot 2^{2^n}$. This is very good for large $n$: for example, for $n=5$, this predicts $2\,605\,029\,347$ connected induced subgraphs, whereas the true count is $2\,524\,817\,935$.