Prerequisites

Basic knowledge of graph theory, linear algebra (eigenvalues) and algebra (abelian groups, polynomial rings, fields).  Any bachelor level courses on graph theory, linear algebra, and rings and fields should be sufficient.

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).

Rules about Homework / Exam

75% of the final grade is determined by a final written exam. The other 25% will be determined by the best 5 out of 6 homework problem sets, provided the mark for the final written exam ist at least 5.0. 

Lecture Notes / Literature

  • Spectral Graph Theory by F. Chung (Book)
  • Extremal Combinatorics With Applications in Computer Science by Stasys Jukna (Book)
  • Research papers to be determined during the course

Note that the book of Stasys Jukna is freely available online and part of the book of F. Chung is available online.

Lecturers: V. Patel (UvA) G. Regts (UvA)