Lecturers - Dr Viresh Patel, Dr Guus Regts TA - Ewan Davies
Time/Location - Friday 14:00-16:45, Room SP C1.112 (Science Park, Amsterdam)
Overview - 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).
Prerequisites - basic knowledge of graph theory and (linear) algebra
Literature -
Lecture notes will be provided during the course
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.
Organisation - Every week there will usually be two hours of lectures and one hour reserved for exercises.
Examination - There will be 4-6 homework problem sets, which determine 25% of the final grade. The other 75% of the final grade is determined by a final written exam.
Lecture notes (for the first half of the course) Updated: 04/06.
Lecture notes (for the second half of the course) Updated: 04/06.
The notes will be updated each week. We may not cover all the material in the notes and some topics may be added. Please email me if you find any mistakes.
Schedule
Lecture 1 - We covered Section 1 of the lecture notes and most of Section 2. We did not go through the proof of Theorem 2.5 (so please read this before next lecture). We covered some of Section 3 (without proofs).
Lecture 2 - We covered Section 3 and Section 4 of the lecture notes.
Lecture 3 - We (informally) discussed how Cheeger's inequality can be used to give an approximation algorithm for graph expansion. We looked at how to compute the eigenvalues of Cayley graphs of abelian groups (Section 5 of the notes).
Lecture 4 - We discussed the zig-zag product and how it can be used to construct a family of constant degree expanders (Section 6 of the notes).
Lecture 5 - We discussed quasirandom graphs (Section 7 of the notes).
Lecture 6 - We discussed Shannon Capacity and the Lovasz theta function (Section 9 of the notes).
Lecture 7 - We covered: Lemma 13.11, Theorem 13.12, Theorem 13.13, Lemma 16.1, Lemma 16.3 (without proof), Lemma 16.5 and Theorem 16.6 from Jukna's book.
Lecture 8 - Covered Terence Tao's proof of the solution to the cap set problem and Hoeffding's bound. See the Section 1 of the lecture notes.
Lecture 9 - Covered the Weak Nullstellensatz, Hilbert's Nullstellensatz with some combinatorial applications. See Section 2 of the lecture notes. We also covered Theorem 16.7 from Jukna's book.
Lecture 10 - Covered the Combinatorial Nullstellensatz and several applications. 16.8, 16.11,16.12,16.13 and 16.14 from Jukna's book.
Lecture 11 - A brief introduction to statistical physics. A proof of the Lee-Yang circle theorem based on Schur products and $\mathbb{D}$-stable polynomials. See Section 3 of the lecture notes (to be written as of yet).
Lecture 12 -
Lecture 13 -
Problem sets
Exercises 1 - All solutions to be handed in at the start of the lecture on Fri 2nd March or by email before that time (to vpatel@uva.nl). Update 17/02: in question 4, one needs to take absolute values; the exercise sheet has been updated accordingly.
Exercises 2 - All solutions to be handed in at the start of the lecture on Fri 16th March or by email before that time (to vpatel@uva.nl).
Exercises 3 - Solutions to Q1-4 to be handed in at the start of the lecture on Fri 13th April or by email before that time (to Ewan Davies (maths@ewandavies.org) and cc to vpatel@uva.nl). There is also a bonus question for which credit is available (but one can obtain full credit from just submitting Q1-4).
Exercises 4 - (Updated 19/04) More questions have been added. Solutions to all questions (including the added ones) to be handed in on 04 May (we encourage you to finish the homework by 20th April).
Exercises 5 - (Updated 15/05) Final version. Solutions to all questions to be handed in by Wednesday 23 May 12.00 by email to Ewan Davies and cc to Guus Regts).
Exercises 6 - (Updated 27/05). Solutions to all questions to be handed in by 14.00 on Friday 01 June.
Note that your best 5 out of 6 marks for the exercises will count towards 25% of your final grade.
Information about the exam
We expect that you know all definitions and statements of results and expect you to be able to apply these to various problems.
We will ask you to state and prove between two and four out of the following results:
In Viresh's part
Theorem 3.2 (eigenvalues of graphs)
Theorem 4.2 (easy direction of Cheeger's inequality)
Theorem 5.1(v) (constructing characters of abelian groups) and Proposition 5.2 (eigenvalues of Cayley graphs)
Theorem 7.1 (Expander mixing Lemma)
Theorem 7.4 (eigenvalues of strongly regular graphs)
Theorem 9.5 Shannon capacity and the Lovász theta function (including Proposition 9.2, Theorem 9.3 and Lemma 9.4)
In Guus's part
From Jukna's book:
-Theorem 16.6 (including the proof of Lemma 16.5)
-Theorem 13.13
-Theorem 16.13
From the notes
-Theorem 1.4
-Proposition 2.2 (you should be able to give the statement of this theorem too!)
-Theorem 3.3
-Theorem 4.1
Please note that while some of the results covered in the course are not on the list above it is very well possible that these results and/or the exercises can be used to generate exam questions.
The exam will consist of 4 questions with 2 on the first half of the course and 2 on the second half.