This is a continuation of a series of posts about online seminars devoted to accessible presentations of some of the most significant mathematical theorems of the 21st century. I am happy to report that last Wednesday Prof. Boaz Klartag delivered a beautiful and accessible talk on sphere packing. If you missed the talk, its recording is now available on YouTube.
The next talk in this seminar series will take place on Wednesday, February 11, 2026, at 4:00 PM (UK time). Prof. Avi Wigderson (Institute for Advanced Study, Princeton, USA) will speak on the topic of expander graphs.
To join the talk, simply click here at the scheduled time. No registration is required. For a full list of upcoming seminars, please visit the seminar webpage: https://th21.le.ac.uk/next-talks/.
For announcements of other talks, as well as descriptions of recent major mathematical breakthroughs, please see the full list of my posts on this blog.
Informally, expander graphs are simultaneously sparse and highly connected. This seemingly paradoxical combination of properties makes them extremely useful in a wide range of applications across mathematics, computer science, and even physics.
Let be a graph with vertex set . For a subset , let denote the number of edges with exactly one endpoint in . The edge expansion ratio of , denoted by , is defined by A sequence of -regular graphs of increasing size is called a family of expanders if there exists a constant such that for all .
This notion admits an equivalent formulation in terms of eigenvalues of the adjacency matrix. The adjacency matrix of an -vertex graph , whose vertices are labeled , is the matrix with entries if vertices and are adjacent and otherwise. The matrix has real eigenvalues, which we order as If is -regular, then and . In 1984, Dodziuk showed that for any -regular graph , In particular, a sequence of -regular graphs forms a family of expanders if and only if there exists such that for all . Thus, the smaller is, the better an expander the graph becomes.
The Alon–Boppana inequality asserts that for any -regular -vertex graph , where denotes a quantity tending to as for fixed . In 1986, Alon conjectured that for every , “almost all” -regular -vertex graphs satisfy the reverse bound In other words, almost all -regular graphs are asymptotically optimal expanders.
This conjecture was proved by Friedman in 2008 (Friedman 2008). For even , a random -regular graph on vertices may be constructed from independent uniformly random permutations of .
Although the statement above addresses even , Friedman also established the conjecture for several other random graph models, including the uniform model on all -regular graphs, thereby resolving the problem completely.
Theorem shows that random regular graphs are expanders with overwhelming probability. However, this result does not provide an explicit construction, and explicit expanders are crucial in many theoretical and practical applications.
One classical source of explicit expanders comes from group theory: Cayley graphs of suitable groups often have strong expansion properties. A strikingly different, purely combinatorial construction was introduced by Reingold, Vadhan, and Wigderson (Reingold, Vadhan, and Wigderson 2002) via the zig–zag product.
For a graph , a -edge path is a triple of vertices such that and are edges of . The graph has the same vertex set as , with an edge between and whenever there exists a -edge path from to in .
Let . A -regular graph is called -coloured if each edge is labeled by an element of in such a way that no two edges sharing a vertex have the same label. For a vertex and a label , let denote the neighbor of along the edge labeled .
Let be a -regular -coloured graph on , and let be a -regular -coloured graph on . The zig–zag product is the -regular graph on in which, for all , , and , there is an edge connecting
Explicit expander constructions such as these play a fundamental role in modern theoretical computer science. Many randomized algorithms for combinatorial problems can be derandomized by replacing random graphs with carefully constructed expanders, leading to efficient deterministic algorithms with strong performance guarantees.