Course info

Prerequisites

Much of the course is about graphs and it will help but is not essential to have some familiarity with graphs and their basic properties (although this can easily be picked up along the way). In addition we will use the notions and basic properties of eigenvalues/eigenvectors, abelian groups, polynomial rings, fields, ideals, tensors, tensor products - all of what is needed is typically covered in any undergraduate mathematics degree, and much of it can also be easily picked up along the way.

Aim of the course

The application of algebraic methods in combinatorics has been remarkably successful in recent years. Examining combinatorial problems from an algebraic perspective also yields connections to combinatorial geometry, probability theory and theoretical computer science. In this course we study some of the most important of these methods and their applications. The two main themes are spectral graph theory and the polynomial method.

Spectral graph theory reveals fundamental information about a graph from its spectrum, i.e., the eigenvalues of the graph's adjacency matrix (or sometimes its Laplacian). We will study three important notions in graph theory from the spectral perspective: graph expansion and the Cheeger inequality, quasirandomness, and graph partitioning. Graph expansion plays an important role in the analysis of random walks which in turn leads to fast algorithms in computer science. Quasirandomness is a measure of how random-like a graph is (a fundamental concept in extremal combinatorics which is at the heart of Szemeredi's regularity lemma for example). Partitioning a graph into parts that interact only weakly is of fundamental practical importance and we will see how spectral techniques can be used to obtain such partitions.

The polynomial method is a relatively recent innovation in combinatorics borrowing some of the philosophy of algebraic geometry. We cover Hilbert's Nullstellensatz and Alon's combinatorial Nullstellensatz and apply these to problems in additive number theory and graph colouring. We treat some very recent applications of the polynomial method to cap set problems. We will also look at stable polynomials to give a construction of Ramanujan graphs (an important family of expander graphs).

Lecturers

Viresh Patel and Guus Regts