Expander graphs from Cayley graphs of groups where every generating set works

Add to your list(s) Download to your calendar using vCal

• Oren Becker (Cambridge)
• Thursday 30 January 2025, 14:30-15:30
• MR12.

If you have a question about this talk, please contact ibl10.

A family of k-regular finite graphs is expanding if the graphs are uniformly highly connected. More precisely, for every partition V(X) = A \cup B of the set of vertices of a graph X in the family, the number of edges connecting A and B must be at least c min{|A|, |B|}, where c>0 is independent of X, A and B.

Such families were first constructed by random methods, but explicit constructions were desirable for applications, e.g. for derandomization of algorithms.

Many families of expander graphs have been constructed as Cayley graphs of non-abelian groups G, i.e. taking G itself as the set of vertices, and connecting vertices g and h with an edge if hg^{-1} belongs to a fixed symmetric generating set S of G.

Much care has been taken in choosing the generating sets S, and in some cases this was shown to be necessary. However, our new result shows that for many standard families of groups, every generating set works.

The talk will begin with a gentle introduction to expander graphs.

Based on joint work with Emmanuel Breuillard.

This talk is part of the Combinatorics Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Combinatorics Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.