Return to Answer

Andrew Newman just posted a preprint to the arXiv, showing that for every prime $p$ and $d \ge 2$, you can get $p$-torsion in homology $H_{d-1}(K)$ with only $O(\log^{1/d} p)$ vertices. (The implied constant depends on $d$, but not on $p$. This is best possible, up to a constant factor.

His construction starts with something similar to what Speyer describes above, which gets you a complex with $O( \log p)$ vertices. Then he applies the probabilistic method, taking a certain carefully chosen random quotient of the complex, gluing together vertices in a random way. This doesn't affect torsion in homology. The problem is that it might not result in a simplicial complex. But Newman uses the Lovász local lemma to show that with positive probability, it does. Hence there exists a vertex identification that works.

Andrew Newman just posted a preprint to the arXiv, showing that for every prime $p$ and $d \ge 2$, you can get $p$-torsion in homology $H_{d-1}(K)$ with only $O(\log^{1/d} p)$ vertices. (The implied constant depends on $d$, but not on $p$.) This is best possible, up to a constant factor.

His construction starts with something similar to what Speyer describes above, which gets you a complex with $O( \log p)$ vertices. Then he applies the probabilistic method, taking a certain carefully chosen random quotient of the complex, gluing together vertices in a random way. This doesn't affect torsion in homology. The problem is that it might not result in a simplicial complex. But Newman uses the Lovász local lemma to show that with positive probability, it does. Hence there exists a vertex identification that works.

Andrew Newman just posted a preprint to the arXiv, showing that for every prime $p$ and $d \ge 2$, you can get $p$-torsion in homology $H_{d-1}(K)$ with only $O(\log^{1/d} p)$ vertices. (The implied constant depends on $d$, but not on $p$. This is best possible, up to a constant factor.

His construction starts with something similar to what Speyer describes above, which gets you a complex with $O( \log p)$ vertices. Then he applies the probabilistic methods, taking a certain carefully chosen random quotient of the complex, gluing together vertices in a random way. This doesn't affect torsion in homology. The problem is that it might not result in a simplicial complex. But Newman uses the Lovász local lemma to show that with positive probability, it does. Hence there exists a vertex identification that works.

Andrew Newman just posted a preprint to the arXiv, showing that for every prime $p$ and $d \ge 2$, you can get $p$-torsion in homology $H_{d-1}(K)$ with only $O(\log^{1/d} p)$ vertices. (The implied constant depends on $d$, but not on $p$. This is best possible, up to a constant factor.

His construction starts with something similar to what Speyer describes above, which gets you a complex with $O( \log p)$ vertices. Then he applies the probabilistic method, taking a certain carefully chosen random quotient of the complex, gluing together vertices in a random way. This doesn't affect torsion in homology. The problem is that it might not result in a simplicial complex. But Newman uses the Lovász local lemma to show that with positive probability, it does. Hence there exists a vertex identification that works.

Andrew Newman just posted a preprint to the arXiv, showing that for every prime $p$ and $d \ge 2$, you can get $p$-torsion in homology $H_{d-1}(K)$ with only $O(\log^{1/d} p)$ vertices. (The implied constant depends on $d$, but not on $p$. This is best possible, up to a constant factor.

His construction starts with something similar to what Speyer describes above, which gets you a complex with $O( \log p)$ vertices. Then he applies the probabilistic methods, taking a certain carefully chosen random quotient of the complex, gluing together vertices in a random way. This doesn't affect torsion in homology. The problem is that it might not result in a simplicial complex. But Newman uses the Lovász local lemma to show that with positive probability, it does. Hence there exists a vertex identification that works!

Andrew Newman just posted a preprint to the arXiv, showing that for every prime $p$ and $d \ge 2$, you can get $p$-torsion in homology $H_{d-1}(K)$ with only $O(\log^{1/d} p)$ vertices. (The implied constant depends on $d$, but not on $p$. This is best possible, up to a constant factor.

His construction starts with something similar to what Speyer describes above, which gets you a complex with $O( \log p)$ vertices. Then he applies the probabilistic methods, taking a certain carefully chosen random quotient of the complex, gluing together vertices in a random way. This doesn't affect torsion in homology. The problem is that it might not result in a simplicial complex. But Newman uses the Lovász local lemma to show that with positive probability, it does. Hence there exists a vertex identification that works.