Small simplicial complexes with prescribed torsion in homology (Q2316798)

Let \(G\) be a finite Abelian group. For \(d\geq 2\), define \(T_d(G)\) to be the smallest number \(n\) for which there exists a simplicial complex \(X\) of dimension \(d\) with \(n\) vertices whose torsion part \(H_{d-1}(X)_T\) of the \((d-1)\)st integral homology group is isomorphic to \(G\). The author provides upper and lower bounds for the size of \(T_d(G)\). Explicitly, there exist constants \(c_d\) and \(C_d\) for which \(c_d\log^{1/d}{|G|}\leq T_d(G)\leq C_d\log^{1/d}{|G|}\). The lower bound was previously established by \textit{G. Kalai} [Isr. J. Math. 45, 337--351 (1983; Zbl 0535.57011)]. The upper bound is obtained in two steps. The first step is explicit: a simplicial complex \(Y\) with at most \(O(\log{|G|})\) vertices and \(H_{d-1}(Y)_T\cong G\) is constructed. The second step is non-explicit: a probablistic argument is used to show that there exists a proper coloring of the vertices of \(Y\) with \(O(n^{1/d})\) colors such that the simplicial complex \(X\) determined by the coloring satisfies \(H_{d-1}(X)_T\cong H_{d-1}(Y)_T\).