Algebraic Methods in Combinatorics

Course manual 2024/2025

Course content

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.

Eigenvalues of graphs contain fundamental information about a graph. We will study them in the form of the characteristic polynomial of graphs. We will look at enumerative properties of the characteristic polynomial. The theory of the characteristic polynomial includes interlacing and Christoffel-Darboux formula. We will then study the matching polynomial where the analogous techniques lead to several proofs of its real-rootedness and its version of Christoffel-Darboux identities. We will then look at more current results in the field. 

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 application of zero freeness of certain combinatorially defined polynomials to perfect matchings and independent sets.

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.

Study materials

Literature

• We will make lecture notes available. In addition we will use the following resource:

  • Extremal Combinatorics With Applications in Computer Science by Stasys Jukna (This book is online available)

Objectives

• Student should know the definitions the results from the course as well be able to reproduce the proofs of the main results.
• The student should be able to apply the interlacing theorem to spectral graph theoretical problems.
• The student should be able to apply the polynomial methods to solve several types of combinatorial problems.
• The students should be able to solve novel problems with the algebraic methods/tools as developed in the course.
• The student should be able to come up with variations of techniques from the course for related problems.

Teaching methods

• Lecture
• Self-study

Learning activities

Attendance

This programme does not have requirements concerning attendance (TER-B).

Assessment

In case a student does not pass the course, only the final exam can be retried. 
The final grade after a resit examination, will be computed as 0.75 (75%) hertentamen and 0.25 (25%) assignments, provided the grade for the retake (hertentamen) is at least a 5.

Assignments

The best 5 out of 6 homework grades will count 25% towards the final grade, provided the grade for the exam is at least a 5.

Fraud and plagiarism

The 'Regulations governing fraud and plagiarism for UvA students' applies to this course. This will be monitored carefully. Upon suspicion of fraud or plagiarism the Examinations Board of the programme will be informed. For the 'Regulations governing fraud and plagiarism for UvA students' see: www.student.uva.nl

Course structure

Contact information

Coordinator

• dr. Guus Regts

Staff

• dr. K. Guo