Computer Science/Discrete Mathematics Seminar I

In theoretical computer science, an increasingly important role is being played by sparse high-dimensional expanders (HDXs), of which we know two main constructions: "building" HDXs [Ballantine'00, ...] and "coset complex" HDXs [Kaufman--Oppenheim'20, ...].  Both constructions have variants for groups of Lie type, but the simplest "A_d-type" ones are the most commonly studied.  Nevertheless, recent major results in property testing and probabilistically checkable proofs were unlocked via topological properties of the more 'exotic' C_d-type building HDXs.

Motivated by this, but also by the fact that coset complex HDXs are easier to understand, we investigated the topological properties (cosystolic/coboundary expansion) of coset complexes HDXs over other Chevalley groups.  In particular, we obtain the "B-type" generalization of a recent result of Kaufman-Oppenheim [KO21], which showed that the A_3-type coset complex HDXs have good 1-coboundary expansion in their links, and thus yield 2-dimensional topological expanders.

These topological considerations are closely related to group theory; indeed, the crux of Kaufman--Oppenheim's proof was a result of Biss and Dasgupta about small presentations of the unipotent group over F_q.  The analogous result in the B_d-type case apparently fails; but, we show how to establish the topological result anyway, through a combination of large computer-assisted rank computations, and long group-theoretic computations (that have recently been Lean-verified, in a separate project).

Joint work with Noah G. Singer (Carnegie Mellon).