1) Prerequisites
Linear Algebra, polynomial rings and ideals, finite fields and graph theory at bachelor level (in mathematics). These correspond to the bachelor courses, Lineaire Algebra, Algebra 2 and Inleiding Grafentheorie at the University of Amsterdam.
2) 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/algebraic 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. We will study the characteristic polynomial using walk generating functions and prove the Interlacing Theorem. We will give graph theoretical applications of this powerful tool, including various spectral bounds for graph parameters. We will extend these algebraic techniques to the matching polynomial, in particular to an analogous interlacing theorem. We will then give applications of this theory, as well as extended techniques such as Christoffel-Darboux identities.
We use some of the machinery for the matching polynomial and combine this with the theory of stable polynomials to give construction of Ramanujan graphs (an important family of expander graphs) and to bound the number of perfect matchings in regular bipartite graphs.
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 recent applications of the polynomial method to cap set problems.
3) Rules about Homework/Exam
The final grade is computed from two components: exam component worth 90% and a quiz component worth 10%.
There will be homework assignments, but these will not be graded. At least 50% of the exam questions will consist of problems identical or nearly identical to homework problems. During the exercise classes there will be the opportunity to ask questions about the homework. Students will be given the opportunity to ask for feedback on worked out problems.
There will be bi-weekly AI-literacy quizzes in which the students are asked to identify the correct solution of a homework problem that is solved by AI in various ways (or a similar task). Quizzes are graded for correctness, and students receive feedback on whether their answers are right or wrong, but the quiz component of the final grade is based on participation only: students receive full marks as long as they complete the quiz, regardless of correctness, provided their written exam grade is at least a 5.5. In case their exam grade is below a 5.5, then the final garde equals the exam grade. The quizes do not count towards a retake exam.
4) Lecture notes/Literature
Most of the course will be based on written lecture notes for the course (will be provided at the start of the course.
A few lectures will be based on the book: Extremal Combinatorics With Applications in Computer Science, by Stacys Jukna
-
Optional reading: Algebraic Combinatorics, by Chris Godsil
5) Lecturers
Krystal Guo,
Guus Regts.
- Docent: Krystal Guo
- Docent: Guus Regts