Latin squares, designs, and high-dimensional expanders

Expander graphs have many wonderful properties: They are highly connected, pseudorandom, and random walks on expanders are rapidly mixing. The study of these objects has been immensely useful and fruitful for both applicative and theoretical fields. Recently, there has been a lot of interest in the study of generalizations of expander graphs to d-uniform hypergraphs. Several competing definitions have been proposed, each corresponding to a different property of expander graphs. Understanding these definitions, their applications, and the relations between them is the goal of this emerging field.

In a joint work with Alexander Lubotzky and Ron Rosenthal, we proved the existence of bounded degree coboundary expanders, a concept that generalizes high connectivity in graphs. Our work makes use of Peter Keevash’s recent construction of designs: We show that the union of a constant number of designs constructed according to Keevash’s random construction is with high probability a good coboundary expander.

The expander mixing lemma quantifies the extent to which an expander graph is pseudorandom. In a joint work with Nati Linial, we asked if there exist pseudorandom designs. In particular, we conjectured that a typical Latin square design is pseudorandom. This has implications for the Algebraic concept of quasirandom groups, introduced by Gowers. Our conjecture implies that there exist maximally quasirandom quasigroups, and we prove this fact.

There remain many promising directions for further research.