Lecturers - Dr Viresh Patel. (There may be occasional lectures by Dr Guus Regts).
Time/Location - Friday 14:00-16:45, room SP D1.112 (week 6 - 15) and room SP C1.112 (week 17 - 21) (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).
This is a rough guide to the course, although alterations may be made as we progress.
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/discussion.
Examination - There will be 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
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 or let me know during lectures if you find any mistakes.
Schedule
Lecture 1 - (Lecture notes) We covered everything in the lecture notes except the proofs of Theorem 2.5 and Theorem 3.2 (iiii) and (iv). Please read those for yourself and raise any questions next time. You can find the first problem set below - you should be able to do all the questions except the parts of Q1 and 2 that ask you to compare with Cheeger's inequality.
Lecture 2 - (Lecture notes) We covered Cheeger's inequality. You should now be able to do all questions on the first problem set.
Lecture 3 - (Lecture notes) We discussed informally how to quickly find the second eigenvector of the Laplacian in order to give a good spectral partitioning algorithm. We also informally discussed extensions of Cheeger's inequality to non-regular graphs and higher order Cheeger inequalities. This is not examinable and so not in the notes. We discussed Cayely graphs and how to find the eigenvectors and eigenvalues (which is in the notes).
Lecture 4 - (Lecture notes) We discussed the zig-zag product and how it can be used to construct a family of constant degree expanders.
Lecture 5 - (Lecture notes) We discussed the Shannon capacity of a graph and determined the Shannon capacity of the 5-cycle.
Lecture 6 - (Lecture notes) We discussed quasirandom graphs.
Lecture 7 - We looked at the linear algebra method covering the following material from the book Extremal Combinatorics With Applications in Computer Science by Stasys Jukna: Theorem 13.7 (graph decompositions) Lemma 13.11 (independence criterion) Theorem 13.12 (two-distance sets) and Theorem 13.13 (Frankl-Wilson Theorem).
Lecture 8 - We looked at the polynomial method covering the following material from Extremal Combinatorics With Applications in Computer Science by Stasys Jukna: Lemma 16.1, Lemma 16.3, Theorem 16.6 (which uses Lemma 16.5), Theorem 16.7, Theorem 16.8. Two further exercises have been added to the Exercises 4.
Lecture 9 - We looked at 4 applications of the Combinatorial Nullstellensatz, namely 16.10/16.11, 16.12, 16.13, 16.14 in Jukna's book. I also gave a little background on some of these results.
Lecture 10 - (Lecture notes) We saw the solution of the capset problem (specifically, Tao's proof using slice rank). In the printed notes (to be uploaded), you can find both Tao's proof and the original proof (as well as the proof of the Hoeffding bound, which was not covered in lectures).
Lecture 11 - (Lecture notes) We discussed further applications of the Nullstellensatz, We also discussed D-stable polynomials, the cut polynomial and the Lee-Yang theorem (which will be proved next time).
Lecture 12 - (Lecture notes) We finished the proof of the Lee-Yang theorem and discussed the independence polynomial and matching polynomial of a graph and where their roots lie.
Lecture 13 - Revision
Lecture notes (final version) - This is the final version of the lecture notes. These will be updated to correct any mistakes that are found.
-update (09/06): The expression at the bottom of p6 had two typos, which have been corrected.
-update(09/06): In the statement of Prop 5.2, the characters are orthonormal after a factor of 1/|Gamma| has been included.
-updated(12/06): On the last page in the displayed equation there was a factor w(uv) missing and correspondingly twice more in the paragraph that follows.
Problem sets
There will be 6 sets of exercises in total: your best 5 out of 6 marks for the exercises will count towards 25% of your final grade. All exercises should be handed in, but not all will be graded.
Exercises 1 - All solutions to be handed in at the start of the lecture on Fri 22nd Feb or by email before that time (to vpatel@uva.nl).
Exercises 2 - Solutions to questions 1, 2, 3 to be handed in at the start of lecture on Friday 08 Mar or by email before that time (to vpatel@uva.nl).
Exercises 3 - Solutions to questions 1, 2, 3, 4 to be handed in by Friday 29 Mar. There is no lecture on that day so either the homework should be put in my pigeonhole at the KdVI (Nikhef building, 3rd floor) or emailed to vpatel@uva.nl. [Correction: Q4(a) ends with "and deduce that ...": this should have come at the end of Q4(b),]
Exercises 4 - There are now 5 questions of this sheet (updated: 12/04). Solutions to all exercises to be handed in at the start of the lecture on Fri 26th April or by email before that time (to vpatel@uva.nl).
Exercises 5 - Solutions to all exercises to be handed in at the start of the lecture on Fri 10th May or by email before that time (to vpatel@uva.nl). You should be able to attempt all questions - one further question may be added next week. Update: I have decided not to add any further questions (so solutions to 5 questions to be handed in on Fri 10th May).
Exercises 6 - Update (18/05): there are now 4 exercises on this sheet. Solutions to all exercises to be handed in at the start of the lecture on Fri 24th May or by email before that time (to vpatel@uva.nl).
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, which will constitute around 40% of the marks:
First half
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 6.5 Shannon capacity and the Lovász theta function (including Proposition 6.2, Theorem 6.3 and Lemma 6.4)
Theorem 7.1 (Expander mixing Lemma)
Theorem 7.4 (eigenvalues of strongly regular graphs)
Second half
From Jukna's book:
-Theorem 16.6 (including the proof of Lemma 16.5) [Solution of Kekaya problem]
-Theorem 13.13 [Frankl-Wilson Theorem about L-intersecting families]
-Theorem 16.13 [Regular subgraphs via Combinatorial Nullstellensatz ]
From the notes:
-Lemma 8.4 / Theorem 8.4 [Capset problem]
-Proposition 9.2 and 9.4 [Applications of Hilbert Nullstellensatz]
-Theorem 10.3 [Lee-Yang Theorem]
-Theorem 11.3 [zeros of matching polynomial are real]
The exam will consist of 4 questions with 2 on the first half of the course and 2 on the second half.
Exam Solutions 2019