On graphs, homology bases, and triangulated homology spheres

Karim Adiprasito, Marc Lackenby, Juan Souto, Geva YashfearXiv 2025 · DOI · arXiv

TL;DR

This paper builds a rigorous bridge between graph theory and manifold topology by showing that counting triangulations of 3D spheres is asymptotically equivalent to counting 3-regular graphs with "short" homology bases. The authors use this connection to prove the existence of sphere triangulations with expander dual graphs, resolving a long-standing open question in geometric combinatorics.

What Problem Does This Paper Address?

The central mystery the authors tackle is the asymptotic enumeration of triangulations. If you have a manifold (like a sphere), how many ways can you glue $N$ "triangles" (simplices) together to form it? Mikhail Gromov famously asked if this number grows exponentially or superexponentially with $N$.

While it's known that the number of triangulations grows at least exponentially, finding an upper bound is much harder. Furthermore, counting these objects in high dimensions is notoriously difficult. This paper addresses two specific challenges:

  1. Dimensional Reduction: Can we relate the complexity of counting high-dimensional manifolds to the 3D case?
  2. Structural Properties: Can the "dual graph" of a sphere triangulation (where vertices are the $d$-dimensional "triangles" and edges represent shared faces) be an expander graph—a graph that is simultaneously sparse and highly connected?

Methods

The authors develop a sophisticated "thickening" construction that moves from simple combinatorial objects to complex topological ones:

  • Graph to 2-Complex: They start with a graph and a basis for its first homology (cycles). They "fill in" these cycles with 2D disks to create a 2-complex.
  • Handle Theory: They then "thicken" this 2-complex into a $d$-dimensional manifold using handlebodies. Specifically, they use 0-handles for vertices, 1-handles for edges, and 2-handles for the 2D disks.
  • Injectivity via Coloring: To ensure that different input graphs don't accidentally produce the same triangulation (which would ruin the counting argument), they develop a method to "encode" information into the triangulation using facet colorings.
  • Mapping Telescopes: To construct the expander spheres, they use "mapping telescopes" of graph covers. By stacking layers of graphs that cover each other, they build a 2-complex whose 1-skeleton is an expander, which then dictates the expander property of the resulting manifold's dual graph.

Datasets

Not applicable. This is a theoretical mathematics paper; it does not use empirical datasets or benchmarks. It relies on formal proofs and constructions within the framework of PL (Piecewise Linear) topology and algebraic graph theory.

Key Insights and Ideas

  • 3D is the "Master" Dimension: The paper proves that if the number of $d$-dimensional triangulated spheres grows superexponentially for any $d \ge 3$, then it must also grow superexponentially for $d=3$. This identifies 3D as the fundamental bottleneck for manifold complexity.
  • The Power of "Short" Bases: The complexity of a manifold's triangulation is intimately tied to how "short" the cycles are that generate its homology. By focusing on graphs with homology bases of bounded length, they can control the size of the resulting manifold.
  • Expanders in Topology: The construction of spheres with expander dual graphs is a major "aha moment." It shows that spheres can be triangulated in a way that is "globally well-connected" despite being locally simple (bounded vertex degrees). This answers a question posed by Gil Kalai.

Key Results

  • Theorem 4 (Counting Equivalence): The number of isomorphism types of $d$-manifolds with $N$ simplices is bounded above and below by the number of 3-regular graphs with $N$ vertices that have "short" homology bases (up to a constant factor in $N$).
  • Theorem 6 (Expander Spheres): For every $d \ge 3$, there exists an infinite family of $d$-sphere triangulations whose dual graphs are $(d+1)$-regular expanders.
  • Bounded Geometry: These expander triangulations have a uniform bound on the number of simplices incident to any single vertex, meaning they don't achieve their "connectedness" simply by having a few massive "hub" vertices.

Limitations and Future Work

  • Dimension 2 is Excluded: The results specifically apply to $d \ge 3$. The 2D case (surfaces) is much better understood and behaves differently because the fundamental group and homology are more constrained.
  • The Growth Rate Remains Open: While the paper proves that counting manifolds is equivalent to counting specific graphs, it doesn't actually solve the underlying question: is the growth exponential or superexponential? It simply moves the goalposts to a more manageable field (graph theory).
  • Constructive vs. Existential: While the authors provide a construction, the resulting triangulations are very large. Optimizing these constructions for smaller $N$ remains a challenge for computational topology.

Summary updated

Abstract

We describe a construction that takes as input a graph and a basis for its first homology, and returns a triangulation of a 3-dimensional homology sphere. This makes precise an idea of M. Gromov and A. Nabutovski. The immediate application, essentially described by Gromov, is to translate problems about asymptotics of homology sphere triangulations to asymptotic counting problems for constant-degree graphs with "short" homology bases. We construct families of 3- sphere triangulations with dual graphs that are expanders, answering a relaxation of a question asked by G. Kalai. Our results also imply that if the number of d-dimensional triangulated homology spheres with n facets is superexponential in n for some d then the same holds for d = 3.
BibTeX
@misc{adiprasito2025graphs,
  author = {Karim Adiprasito and Marc Lackenby and Juan Souto and Geva Yashfe},
  title = {{On graphs, homology bases, and triangulated homology spheres}},
  year = {2025},
  eprint = {2509.06275},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.06275},
  howpublished = {arXiv},
}

Loading related content...

Figure