MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
@FernandoMuro, I don't see the connection. Since the question seems to be 'global' (about a sequence of complexes) rather than 'local' (about a sequence of objects, eg loops, in a fixed complex), perhaps it's better to think about a connection with the triviality problem for the fundamental group. Now, I believe it's unknown whether the triviality problem is undecidable for aspherical 2-complexes (which is the sort of thing one would want here, since one would like the fundamental group to determine the homotopy type), but let's imagine for the sake of argument that this problem is... – HJRW Feb 4 at 9:56
... indeed undecidable. This would mean that there is a recursive sequence of 2-complexes $X_i$ with the property that the set of integers $i$ such that $X_i$ is contractible is recursively enumerable but not recursive. Furthermore, by pruning the list, we may as well assume that $X_i$ has at least $i$ vertices. Now, for the set of complexes $\{X_i\}$, we clearly have that $\gamma(n)\leq n$, which is a far stronger upper bound than one gets for general complexes. But of course we still have undecidability. The moral here is that even very strong statements about $\gamma(n)$... – HJRW Feb 4 at 10:00
up vote 7 down vote accepted

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|cite|improve this answer

I would expect that the answer for the Dedekind problem on the number of simplicial complexes on $n$ labelled vertices should essentially give the right behavior (doubly exponential with $n$) also for homotopy type. (The difference between labelled and unlabelled vertices is at most $n!$ so it is negligible.)

share|cite|improve this answer
I understand why the number of labelled and unlabelled complexes on $n$ vertices differs by the $n!$ factor of course, but it is not clear why counting up to homotopy shouldn't make a bigger difference than that factor. – Vidit Nanda Feb 3 at 20:17
Dear Vidit, This is my expectation. But maybe I am pushing it to assume it will be doubly exponential. Since you dont specify the dimension it is reasonable to think it will typically be n/2. Which also mean that the complex will typically be simply connected. The possibilities for sequences of Betti numbers are well known. I think there are roughly $2^{n^2}$ possible sequences of Betti numbers. The point is that these sequences can be very different for different characteristics. But I admit that the guess that the number is doubly exponential is pretty wild. – Gil Kalai Feb 3 at 23:37

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.