Expanders and growth in groups

These are the web pages for a set of seminars to be given at the University of Western Australia in 2010. The seminars constitute an introduction to the area of “growth in groups”, and the connection between growth and “expander graphs”.

The research group at UWA is very strong in group theory and in finite geometry, hence I will emphasise these aspects of the subject. I will also assume familiarity with results from these areas.

  • Recommended background reading can be found here.
  • Lectures (I will add lecture notes after the lecture is given):
    1. Sum-product (12 noon, Tues 4 May 2010; notes now available)

      We introduce the idea of growth in groups, before focussing on the abelian
      setting. We take a first look at the sum-product principle, with a brief
      foray into the connection between sum-product results and incidence
      theorems.

      We then focus on Helfgott’s restatement of the sum-product principle in
      terms of groups acting on groups.

    2. Growth in groups of Lie type (11am, Fri 7 May 2010; notes now available)

      Since Helfgott first proved that “generating sets grow” in SL_2(p) and
      SL_3(p), our understanding of how to prove such results has developed a
      great deal. It is now possible to prove that generating sets grow in any
      finite group of Lie type; what is more the most recent proofs are very
      direct – they have no recourse to the incidence theorems of Helfgott’s
      original approach.

      We give an overview of this new approach, which has come to be known as a
      “pivotting argument”. There are five parts to this approach, and we
      outline how these fit together.

    3. Escape (11am, Fri 14 May 2010); notes now available)

      The principle of “escape from subvarieties” is the first step in proving
      growth in groups of Lie type. We give a proof of this result, and its most
      important application (for us) – the construction of regular semisimple
      elements.

      We then examine other related ideas from algebraic geometry, in particular
      the idea of non-singularity.

    4. Growth in soluble subgroups of GL_r(p) (11am, Wed 21 Jul 2010; notes will not be written up for this – a preprint will appear on the arXiv in due course.)

      We show how to reduce the study of exponential growth in
      soluble subgroups of GL_r(p) to the nilpotent setting. We make use of ideas based on the sum-product phenomenon, as well as some machinery from linear algebraic groups. We will not assume any background from these areas. This lecture is based on new results of the lecturer and Helfgott.

    5. An introduction to expanders (11am, Fri 23 Jul 2010; notes now available)

      This is a background lecture preparing the way for the final lecture, where we
      connect results on growth in simple groups to the explicit construction of
      families of expanders. In this lecture we will define what we mean by a
      family of expanders, stating (and sometimes even proving!!) background
      results that will be important later.

      We will also try to explain why expanders are of such interest to so many
      different groups of people.

    6. Using growth results to explicitly construct expanders (1pm, Tue 27 Jul 2010; notes now available)

      We outline the method of Bourgain and Gamburd. They were the
      first to use
      results concerning growth in simple groups to explicitly construct
      expander graphs. Let S be a set in SL_2(Z) and define S_p to be the
      natural projection of S modulo p. Now let G_p be the Cayley graph of
      SL_2(p) with respect to the set S_p. Bourgain and Gamburd give precise
      results as to when the set of graphs {G_p : p a prime} forms a family of
      expanders. They make crucial use of the result of Helfgott (encountered in Seminar 2) which states that “all generating sets in SL_2(p)
      grow”.