Fix a prime $p$. What is the smallest integer $n$ so that there is a simplicial complex on $n$ vertices with $p$-torsion in its homology?
For example, when $p=2$, there is a complex with 6 vertices (the minimal triangulation of the real projective plane) with 2-torsion in its homology. I'm pretty sure that it's the smallest possible: with 5 or fewer vertices, there should be no torsion at all. When $p=3$, there is a complex with 9 vertices (a triangulation of the mod 3 Moore space, for instance) with 3-torsion. Is there one with 8 vertices? With $p=5$, there is a complex with 11 vertices, found by randomly testing such complexes on my computer.
We can refine this: fix $p$ and also a positive integer $d$. What's the smallest $n$ so that there is a simplicial complex $K$ on $n$ vertices with $p$-torsion in $H_d(K)$? Or we can turn it around: for fixed $n$, what kinds of torsion can there be in a simplicial complex on $n$ vertices?
(A paper by Soulé ("Perfect forms and the Vandiver conjecture") quotes a result by Gabber which leads to a bound on the size of the torsion for a fixed number $n$ of vertices; however, this bound is far from optimal, at least for small $n$.)
Best Answer
UPDATE This version is substantially improved from the one posted at 8 AM.
I now think I can achieve $\mathbb{Z}/p$ using $O( \log p)$ vertices. I'm not trying to optimize constants at this time.
Let $B$ be a simplicial complex on the vertices $a$, $b$, $c$, $a'$, $b'$, $c'$ and $z_1$, $z_2$, ..., $z_{k-3}$, containing the edges $(a,b)$, $(b,c)$, $(c,a)$, $(a',b')$, $(b',c')$ and $(c',a')$ and such that $H^1(B) \cong \mathbb{Z}$ with generator $(a,b)+(b,c)+(c,a)$ and relation
$$2 {\large (} (a,b)+(b,c)+(c,a) {\large )} \equiv (a',b') + (b',c') + (c',a').$$
I think I can do this with $k=6$ by taking damiano's construction with $p=2$ and adding three simplices to make the hexagon $(h_1, h_2, \ldots, h_6)$ homologous to the triangle $(h_1, h_3, h_5)$.
Let $B^n$ be a simplicial complex with $3+nk$ vertices $a^i$, $b^i$, $c^i$, with $0 \leq i \leq n$, and $z^i_j$ with $0 \leq i \leq n-1$ and $1 \leq j \leq k-3$. Namely, we build $n$ copies of $B$, the $r$-th copy on the vertices $a^r$, $b^r$, $c^r$, $a^{r+1}$, $b^{r+1}$, $c^{r+1}$ and $z^r_1$, $z^r_2$, ..., $z^r_{k-3}$. Let $\gamma_i$ be the cycle $(a^i,b^i) + (b^i, c^i) + (c^i, a^i)$.
Then $H^1(B^n) = \mathbb{Z}$ with generator $\gamma_0$ and relations $$\gamma_n \equiv 2 \gamma_{n-1} \equiv \cdots \equiv 2^n \gamma_0$$
Let $p = 2^{n_1} + 2^{n_2} + \cdots + 2^{n_s}$.
Glue in an oriented surface $\Sigma$ with boundary $\gamma_{n_1} \sqcup \gamma_{n_2} \sqcup \cdots \sqcup \gamma_{n_s}$, genus $0$, and no internal vertices.
In the resulting space, $\sum \gamma_{n_i} \equiv 0$ so $p \gamma_0 \equiv 0$, and no smaller multiple of $\gamma_0$ is zero. We have use $3 + k \log_2 p$ vertices. This is the same order of magnitude as Gabber's bound.