24
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 4
    $\begingroup$ What would an answer to this question say in connection with the word problem via fundamental groups? $\endgroup$
    – Fernando Muro
    Commented Jul 18, 2012 at 22:18
  • 5
    $\begingroup$ 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. $\endgroup$
    – Patricia Hersh
    Commented Jul 19, 2012 at 1:38
  • 1
    $\begingroup$ @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. $\endgroup$
    – Russ Woodroofe
    Commented Jul 19, 2012 at 23:16
  • $\begingroup$ @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... $\endgroup$
    – HJRW
    Commented Feb 4, 2016 at 9:56
  • $\begingroup$ ... 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)$... $\endgroup$
    – HJRW
    Commented Feb 4, 2016 at 10:00

4 Answers 4

Reset to default
13
$\begingroup$

Andrew Newman just posted a preprint to the arXiv showing that the answer is doubly exponential in $n$.

In particular, he showed that the number of homotopy types of simplicial complexes on $n$ vertices is at least $$\exp \left( \exp \left( 0.004n \right) \right),$$ for all large enough $n$.

This matches the upper bound from Dedekind numbers, up to the constant $0.004$.

Newman's result depends on showing that this many different torsion subgroups are possible for homology in dimension $d$, where $d \approx \delta n$ for some small constant $\delta > 0$. The existence proof is partly constructive and partly depends on the probabilistic method.

https://arxiv.org/abs/1804.06787

Improve this answer
$\endgroup$
0
8
$\begingroup$

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

Improve this answer
$\endgroup$
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Vidit Nanda
    Commented Feb 3, 2016 at 20:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – Gil Kalai
    Commented Feb 3, 2016 at 23:37
1
$\begingroup$

The sequence A261005 of OEIS should be helpful, since it is an upper bound. However, I don't know any closed formula for the number of simplicial complexes on n unlabeled vertices (without the homotopy condition).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .