MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## How many simplicial complexes on n vertices up to homotopy equivalence?

Fix a number $n$, and define $\gamma(n)$ to be the number of simplicial complexes on $n$ unlabeled vertices up to homotopy equivalence. It is unlikely that an explicit formula exists, but what is known about the growth of $\gamma(n)$ as $n$ increases?

This seems to be a fairly basic generalization of "how many non-isomorphic graphs on $n$ unlabeled vertices?" but while this problem even has an OEIS entry, I can't find any decent references or calculations for $\gamma$.

Note: I do not mean to ask about the Dedekind number which simply counts all possible simplicial complexes on $n$ vertices without regard to homotopy equivalence.

-
What would an answer to this question say in connection with the word problem via fundamental groups? – Fernando Muro Jul 18 at 22:18
Your question makes me wonder whether the paper "On f-vectors and homology" by A. Bj"orner and G. Kalai would be of help at least with the (much easier??) question of how many different sequences of Betti number are achievable for fixed number of vertices. I don't have access right now to that paper though. – Patricia Hersh Jul 19 at 1:38
@Tricia: A major step in the Björner/Kalai paper is that, by applying algebraic shifting, one can reduce problems relating f-vectors and homology down to shifted complexes. Since shifted complexes are (among other nice properties) always bouquets of spheres, the problem you mention indeed looks quite tractable. – Russ Woodroofe Jul 19 at 23:16

Fernando Muro's argument seems convincing that getting an exact formula is likely to be impossible. But we still might find lower and upper bounds that give us a sense of the asymptotics.

We can get a lower bound by restricting to a subset, like graphs up to homotopy equivalence. This has a pretty nice generating function.

$\sum_{n=0}^\infty \gamma(n) q^n=\frac{1}{(1-q)^2(1-q^3)(1-q^4)^2(1-q^5)^3(1-q^6)^4\dots}=\frac{1}{(1-q)^2}\prod_{n=1}^\infty \frac{1}{(1-q^{n+2})^n}$

The reason for this is that you can identify a complex by the number of connected graphs of each Euler characteristic it contains. Then each complex shows up at whatever the minimal $n$ is to express it, which is just a sum over the graphs, and at each larger $n$. Since the number of possible Euler characteristics is quadratic in $n$, the number of new types at each $n$ is linear. You have two extra $1-q$ terms, one to account for the 1-vertex graph, and one to account for homotopy types showing up after the minimal $n$.

-