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

2012-07-18T21:47:49Z

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.

Answer by Will Sawin for How many simplicial complexes on n vertices up to homotopy equivalence?

2012-07-19T19:00:26Z

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

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

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

Answer by Will Sawin for How many simplicial complexes on n vertices up to homotopy equivalence?