BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Expander graphs from Cayley graphs of groups where every generatin
 g set works - Oren Becker (Cambridge)
DTSTART:20250130T143000Z
DTEND:20250130T153000Z
UID:TALK227194@talks.cam.ac.uk
CONTACT:103978
DESCRIPTION: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 numbe
 r of edges connecting A and B must be at least c min{|A|\, |B|}\,\nwhere c
 >0 is independent of X\, A and B.\n\nSuch families were first constructed 
 by random methods\, but explicit constructions were desirable for applicat
 ions\, e.g. for derandomization of algorithms.\n\nMany families of expande
 r 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 an
 d h with an edge if hg^{-1} belongs to a fixed symmetric generating set S 
 of G.\n\nMuch care has been taken in choosing the generating sets S\, and 
 in some cases this was shown to be necessary. However\, our new result sho
 ws that for many standard families of groups\, every generating set works.
 \n\nThe talk will begin with a gentle introduction to expander graphs.\n\n
 Based on joint work with Emmanuel Breuillard.
LOCATION:MR12
END:VEVENT
END:VCALENDAR