Computer Science/Discrete Mathematics Seminar II

Expander graphs are a staple of theoretical computer science. These are graphs which are both sparse and well connected. They are simple to construct and modify. Therefore they are a central gadget in numerous applications in TCS and combinatorics. High dimensional expanders (HDXs) are the hypergraph analogue of expander graphs. These amazing set systems have already proven useful in recent applications in coding theory, PCPs, Boolean function analysis and extremal combinatorics. However, in contrast to expander graphs, HDXs are notoriously hard to come by. All known bounded degree constructions of HDXs are based on structures from algebraic group theory. As such ``the reason they expand'' may be opaque to the non-experts. It is an important open question to construct HDXs whose properties could be analyzed by elementary means.

In this talk I will present new constructions of HDXs that come from Cayley graphs over $F_2^n$. These constructions build on the ingenous work of Louis Golowich (FOCS, 2023) and rely heavily on the connection between Cayley graphs and the Grassmannian over $F_2^n$. Even though the vertex degrees of these hypergraphs are not uniformly bounded, they are still non-trivially sparse. More importantly, their expansion properties follow from elementary arguments about johnson graphs and subspaces of $F_2^n$. Along the way, we will see how this construction also gives us expanding sparsifications of the Grassmannian, which may be of independent interest.

I will begin the talk with a gentle introduction on HDXs, surveying the definitions, constructions, and applications of these objects. No prior HDX knowledge is assumed on your part. This talk is based on work with Siqi Liu and Avi Wigderson, https://arxiv.org/abs/2411.08839