Semidirect products, group structure, and expander families

11/06/2012 - 12:15pm
11/06/2012 - 1:10pm
Mike Krebs (Cal State LA)

Roughly speaking, expander families are sequences of large, sparse, pseudorandom graphs.  One common method for creating such graphs is the Cayley graph construction, where the vertex set is a group and the adjacency relations are defined in terms of the group structure.  Some sequences of groups yield expander families via this construction, and some do not.  For example, abelian groups never work, whereas after decades of work by many mathematicians a proof was at last completed earlier this year that nonabelian simple groups always do.  It is an open problem to determine which sequences of groups yield expander families.  In this talk, we’ll make the preceding discussion precise (all of the definitions are elementary) and discuss some obstructions to expansion and some preliminary investigations of groups formed by iterating semidirect products of cyclic groups.

Millikan 208 (Pomona College)