Yesterday we submitted on http://arxiv.org/abs/1302.2370 a paper "Extendability of continuous maps is undecidable" claiming that the following problem is undecidable: Given simplicial complexes $X$ and $Y$ and a simplicial map $f:A\to Y$ from a subcomplex $A$ of $X$, decide whether there is a continuous extension $|X|\to |Y|$ of $|f|$. Substantial features:
the undecidability is show by a reduction from the Hilbert's 10th problem, that is, solvability of Diophantine polynomial equation
the undecidability holds even if we require the considered spaces to be $k$-connected for arbitrary $k\ge 1$
Notably, once the dimension of $X$ is less than $2k$ where $k$ is the connectivity of $Y$ (stable range), the problem becomes solvable (in polynomial time when $k$ is fixed), see http://arxiv.org/abs/1211.3093.
I have some idea, but I'm not sure it works well.
First I give a triangulation to $CP^1$: let's say that $CP^1$ is $C$ with a point $\infty$ added. Then we can fix 6 vertices, $0,1,-1,i,-i,\infty$ and divide $CP^1$ in 6 vertices, 12 edges and 8 triangles. Each complex number belongs to one of the 8 triangles according to the sign of its real part, the sign of its imaginary part and whether its modulus is greater or lower than 1.
So there are 26 types of points in $CP^1$: 3 choices for the sign (or zero) for the imaginary part, 3 choices for the sign (or zero) for the real part, 3 choices for the sign of the logarithm of the modulus would yield 27, but it is not possible to have 0 real, 0 imaginary and 1 modulus (we say that $\infty$ has modulus greater than 1, but its imaginary and real parts are 0).
Note that a complex number (not $\infty$) has only 25 types: the ones different from the $\infty$ type.
More generally, every homogeneous $n+1$-tuple $[z_0,\dots, z_n]$ in $CP^n$ has exactly one representative whose first nonzero coordinate is 1. The following coordinates are just complex numbers, so each of them is in one of the 25 types stated before. So we associate to a point in $CP^n$ the following data:
1) The position of the first nonzero coordinate, which is some integer $0\leq k\leq n+1$;
2) the $n-k$-tuple of the types of complex numbers in the preferred representative.
Points with the same data are in the same internal part of the same simplex, and the dimension of a simplex is given by the number of < and > appearing in point 2 (I have no time now to explain in detail, but I hope it's quite clear).
For example, vertices are points of the form $[0,0,0,1,i,0,-i,0,1,-1,0]$, that is, $n+1$-tuplesmade just of $0,1,-1,i,-i$ with the first nonzero coordinate equal to 1.
Best Answer
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.