picture

Recent trends in the study of expanders and high dimensional expanders

February 12-16, 2017 ,
The David Lopatie Conference Centre
Weizmann Institute of Science

Course 1: New trends in expanders based on the method of interlacing polynomials

Instructor: Doron Puder

Lecture 1: Interlacing Polynomials and Ramanujan Graphs of all Degrees
Ramanujan graphs are optimal expander graphs. In 2013, Marcus, Spielman and Srivastava solved a long standing open problem and proved the existence of bipartite Ramanujan graphs of all degrees. The main new tool they use is the method of interlacing polynomials. We will introduce their work, and through it, the method of interlacing polynomials. If time permits, we will also point to a connection with the approximation of a matrix permanent.

Lecture 2: Interlacing Polynomials and the proof of the Kadison-Singer Problem
The initial motivation of Marcus, Spielman and Srivastava in developing the method of interlacing polynomials was in their study of the Kadison-Singer Problem. We will describe their solution to this problem, which is probably the most impressive usage to date of this method.

Lecture 3: Introduction to the Theory of Group Representations
The theory of group representations is a central area in Mathematics since the beginning of the 20th century. It also has a growing set of applications in computer science. We will give a brief introduction to the theory. Our focus will be on representations of the Symmetric Group.

Lecture 4: Card Shuffling and expanders
How long does it take to reach a near perfect random deck of cards if we shuffle the deck by taking two cards at random and swap them? In a beautiful application to Representation Theory, Diaconis and Shahshahani show that O (n log n) swaps lead to a nearly perfect random deck. This manifests a common theme: representation theory can be used to prove certain graphs (mostly Cayley graphs) are expanding.

Lecture 5: Ramanujan Coverings of Graphs
In the final lecture we discuss a more recent result which illustrates how both tools - the method of interlacing polynomials and representation theory - can be combined. Together with Chris Hall and Will Sawin, we generalize the work of Marcus-Spielman-Srivastava and prove the existence of a richer family of bipartite Ramanujan graphs. This approach also suggests a strategy for fast construction of such graphs.