Bounded-degree coboundary expanders

The explanation

Put ten points around a ring and join each point to its two neighbors. Pick five points in a row. Only two links leave that group, so the ratio is 2 to 5, or 0.4. Take a ring of a thousand points and pick half of them in a row. Still only two links leave, and the ratio falls to 0.004. A large ring has a bottleneck.

The Petersen graph does much better. It has ten points, each joined to three others. Check every group of at most five points. At least as many links leave the group as there are points in it. The worst ratio is exactly 1. Networks that keep such a ratio above a fixed number, as they grow, are called expanders. In an expander, the links leaving a group measure how far the group is from nothing or everythingSource 1.

Coboundary expansion carries this idea to higher dimensions. Build a shape from points, links, filled triangles, filled tetrahedra and so on. Such a shape is a simplicial complex, and its pieces are called faces. Choose a set of links. Its coboundary is the set of triangles that contain an odd number of the chosen linksSource 2. Some sets of links have an empty coboundary for a trivial reason: they come from a set of points. Take all links leaving some group of points, and every triangle contains zero or two of them. A complex is a coboundary expander when the converse holds in a strong, measured form. A small coboundary forces the set to be close to one of those trivial sets. The same must hold one level up, two levels up, and so on.

There is a catch. Some complexes have holes, like the hollow inside a doughnut. A hole gives a set whose coboundary is empty, yet it is not close to any trivial set. So coboundary expansion also demands that the complex have no such holes, at every level below the topSource 3.

Mikhail Gromov asked in 2010 for large complexes of this kind with a bounded number of faces at each pointSource 4. In 2019, Lubotzky, Luria and Rosenthal built random expanders in every dimensionSource 5. But in their complexes, the number of faces at each point grows with the sizeSource 6. Evra and Kaufman got bounded-degree complexes in every dimension with a weaker property that allows holesSource 7. Chapman and Lubotzky settled the two-dimensional case in 2025Source 8. Other work did not give the needed absence of holes at every levelSource 9.

This paper proves the remaining case: every dimension from 3 upSource 10. For each such dimension d, it builds a family of ever larger d-dimensional complexes. Every point lies in at most a fixed number of top faces. The expansion constant is the same for every member of the family, at every level below dSource 11. Together with graphs and the two-dimensional case, this gives such expanders in every dimension.

The obstacle was proving there are no holes. A weaker measured inequality was already known for this family of complexes. It measures distance only to sets with empty coboundary, so it tolerates holes. The family comes from matrix groups built from polynomials. Small fixed groups describe the neighborhood of each point, which keeps the number of faces boundedSource 12. The new work shows that every finite member of the family has no holes below the top level. That lets the earlier inequality be upgraded into full coboundary expansionSource 13.

How sure is this? A computer proof checker called Lean has checked a formal version of the construction for every dimension of at least 3. The graph and two-dimensional cases, used to cover every dimension, are separate results. The constants may depend on the dimension. No specialist review of the paper has been published.

What it doesn't show. This does not give explicit values for the degree bound or the expansion constant.