Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
What would an answer to this question say in connection with the word problem via fundamental groups? –  Fernando Muro Jul 18 '12 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 '12 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 '12 at 23:16
add comment

1 Answer

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$.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.