Essentially, my question is how strong a restriction it is to be simply connected.

Here is a way of making this precise: Let's say we want to count simplicial complexes (of dimension 2, though that does not matter much, any fixed dimension is fine) on N simplices that are subject to the following restrictions:

A: every vertex is contained only in a bounded number of simplices (say, 10000).

B: the complex is simply connected.

So properly: How many distinct complexes like this are there? In fact, I only want a rough answer: is it exponential in N, or is it superexponential. Note that if I remove either restriction, the answer is superexponential.

  • 6
    $\begingroup$ When asking this question (which is sort of a stronger version of your question), I learned that there are many models of what a "generic" or "random" simplicial complex should be, and moreover that the answers to questions like this are sensitive to the choice of model. Do you have strong reasons for preferring a model where the "valency" is bounded over, say, a model where there is a constant probability that a given subset is a simplex? $\endgroup$ – Tim Campion 2 days ago
  • 1
    $\begingroup$ You might find some relevant information in the paper of Babson, Hoffman and Kahle: The fundamental group of random 2-complexes. J. Amer. Math. Soc. 24 (2011), no. 1, 1–28. $\endgroup$ – Anthony Quas 2 days ago
  • 1
    $\begingroup$ Are you counting up to isomorphism? (I expect so, just to be sure) $\endgroup$ – YCor yesterday
  • 2
    $\begingroup$ @SamHopkins but counting multiplies by $n!$, which affects the growth rate. $\endgroup$ – YCor yesterday
  • 2
    $\begingroup$ It seems to be that this is an open problem even if you count simplicial complexes with fixed bounded first Betti number. If I am wrong I would be very interested to know. $\endgroup$ – Bruno Martelli yesterday

Here's a rough estimate indicating that indeed, in this "bounded-valency" model, a simplicial complex has nonvanishing fundamental group with high probability. We'll actually conclude something stronger: the number of 2-simplices is bounded with high probability.

Let $N$ be the number of vertices, and let $d$ be the bound on the number of simplices containing a given vertex. Let's think about a 2-complex $X$ in this model as follows:

  • The 1-skeleton $X_1$ of $X$ is a graph with valency bounded by $d$, and so has $\leq Nd/2$ edges. Its fundamental group is a free group on $\leq N(d/2-1)-1$ generators. Let's assume that $X_1$ is connected or at least is dominated by a giant component, and that we're interested in the fundamental group of the giant component.

  • Now each 2-simplex we add can only shrink the fundamental group, so we might as well add in all possible 2-simplices and see that the result is still not simply-connected. The probability that a given pair of vertices is connected by an edge is $\sim (Nd/2) / {N \choose 2} \sim d/N$. So given a vertex and two edges connected to it, the probability that these fit into a triangle is $\sim d/N$. So each vertex is contained in $\sim {d \choose 2}(d/N) \sim d^3/(2N)$ triangles, and so there are a total of $\sim \frac 1 3 N(d^3/(2N)) = d^3/6$ triangles.

That is, the fundamental group of $X_1$, which is free on a number of generators $\sim N(d/2-1)$ growing with $N$, is quotiented by a bounded number of relations $\sim d^3/6$ with high probability. By looking at abelianizations, we can see this implies that $H_1(X) \neq 0$ and in particular that $\pi_1(X) \neq 0$.

Of course, if you take $d \sim 10000$, then the bound on the number of relations is about a trillion, so you need to look at pretty big complexes before you see this behavior emerge :).

I think the main "non-rigorous step" of this argument lies in assuming that the probability for two vertices $v,w$ to be connected by an edge does not go up when we condition on the event that $v,w$ are each connected to a third vertex $u$. This seems very plausible to me (if anything the probability should go down a bit because one of the possible $d$-many vertices for $v$ to be connected to is taken up by $u$ and similarly for $w$), but I'm not sure how to actually justify it.

| cite | improve this answer | |
  • 1
    $\begingroup$ This seems like it's answering a different question than whether the number of simply connected complexes with bounded valence grows exponentially or super-exponentially in $N$. $\endgroup$ – Sam Hopkins yesterday
  • 4
    $\begingroup$ @SamHopkins I'm (sketchily) answering the weaker question of whether the number of simply connected complexes with bounded valence grows more slowly than the total number of complexes with bounded valence, i.e. whether "most" complexes of bounded valence are non-simply-connected. My understanding was that the idea of asking about exponential growth was primarily motivated as a strengthening of the question I've attempted to answer. $\endgroup$ – Tim Campion yesterday

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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