Is being simply connected very rare?

Question

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.

Answer 1

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. I think this points to a deficiency of the "bounded valency" model -- intuitively I would expect a "good" measure on simplicial complexes with $N$ vertices to tell me that the expected number of 2-simplices grows with $N$.

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.

Answer 2

The following does not answer your question, but adding just in case it is helpful.

If you weaken "simply connected" to $H_1(\Delta, \mathbb{Q}) = 0$, and weaken "every vertex is in a bounded number of edges" to "the average number of triangles containing an edge is bounded", then there are super-exponentially many such complexes. This is an old result of Kalai, on enumerating $\mathbb{Q}$-acyclic complexes. https://link.springer.com/article/10.1007/BF02804017 There are $\exp( cn^2)$ such complexes, where $c>0$ is some constant not depending on $n$. For the latest on enumerating $\mathbb{Q}$-complexes, see Linial and Peled: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20841

Andrew Newman and I recently showed that a typical $\mathbb{Q}$-acyclic complex (according to a natural `determinantal measure') is not simply connected. With high probability, the fundamental group is a hyperbolic group of cohomological dimension 2. https://arxiv.org/abs/2004.13572