How many simplicial complexes on n vertices up to homotopy equivalence? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T14:26:39Z http://mathoverflow.net/feeds/question/102587 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/102587/how-many-simplicial-complexes-on-n-vertices-up-to-homotopy-equivalence How many simplicial complexes on n vertices up to homotopy equivalence? Vidit Nanda 2012-07-18T21:47:49Z 2012-07-19T19:00:26Z <p>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?</p> <p>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 <a href="http://oeis.org/A000088" rel="nofollow">OEIS entry</a>, I can't find any decent references or calculations for $\gamma$.</p> <p><strong>Note</strong>: I do not mean to ask about the <a href="http://en.wikipedia.org/wiki/Dedekind_number" rel="nofollow">Dedekind number</a> which simply counts all possible simplicial complexes on $n$ vertices without regard to homotopy equivalence.</p> http://mathoverflow.net/questions/102587/how-many-simplicial-complexes-on-n-vertices-up-to-homotopy-equivalence/102694#102694 Answer by Will Sawin for How many simplicial complexes on n vertices up to homotopy equivalence? Will Sawin 2012-07-19T19:00:26Z 2012-07-19T19:00:26Z <p>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.</p> <p>We can get a lower bound by restricting to a subset, like graphs up to homotopy equivalence. This has a pretty nice generating function.</p> <p>$\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}$</p> <p>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$.</p>