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 $(a^n_0, b^n_0) + (b^n_0, c^n_0) + (c^n_0, a^n_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.

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.

I now think I can achieve $\mathbb{Z}/p$ using $O( (\log p)^2)$ vertices. I'm not trying to optimize constants 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=3$ 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$. 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}$.

Then $H^1(B^n) = \mathbb{Z}$ with generator $(a^n_0, b^n_0) + (b^n_0, c^n_0) + (c^n_0, a^n_0)$ and relation

$$2^n {\large(} (a^0,b^0)+(b^0,c^0)+(c^0,a^0) {\large)} \equiv {\large(} (a^n,b^n) + (b^n,c^n) + (c^n,a^n) {\large)}.$$

Let $p = 2^{n_1} + 2^{n_2} + \cdots + 2^{n_s}$. Build copies of $B^{n_i}$, identifying the triangles $a^0_i$, $b^0_i$, $c^0_i$ for $1 \leq i \leq s$. Call the resulting space $C$. Let $\gamma_i$ be the cycle $(a_i^{n_i}, b_i^{n_i}) + (b_i^{n_i}, c_i^{n_i}) + (c_i^{n_i}, a_i^{n_i})$ and let $\delta$ be the cycle $(a^0, b^0,c^0)$ common to all the $B^{n_i}$. Then $H_1(C) = \mathbb{Z}$, generated by $\delta$, and $\gamma_i \equiv 2^{n_i} \delta$. We have used $3 + k \sum n_i$ vertices.

Glue in an oriented surface $\Sigma$ with boundary $\gamma_1 \sqcup \gamma_2 \sqcup \cdots \sqcup \gamma_s$, genus $0$, and no internal vertices.

In the resulting space, $\sum \gamma_i \equiv 0$ so $p \delta \equiv 0$, and no smaller multiple of $\delta$ is zero. We have $\sum n_i \leq \sum_{n=0}^{\log p} n \leq (1/2) (\log p )^2$.

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 $(a^n_0, b^n_0) + (b^n_0, c^n_0) + (c^n_0, a^n_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.