Lecturers - Dr Viresh Patel, Dr Guus Regts TA - Bart Sevenster
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 -
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.
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.
Schedule
Lecture 1 - We introduced the notion of sparsest cut and edge expansion. We recapped on some basic linear algebra and proved the variational characterisation of eigenvalues. We stated a result relating eigenvalues of the Laplacian to the number of (bipartite) components of the graph. (This material can be found in Chapter 1 of the lecture notes of Luca Trevisan here.)
Lecture 2 - We proved Thm 1.7 which relates eigenvalues fo the Laplacian to the number of bipartite components of the graph. We then proved Cheeger's inequality. (This material can be found in Chapter 2 of these notes.)
Lecture 3 - We saw how the Spectral Partitioning algorithm (from the proof of Cheeger's inequality) can be combined with the Power Method (which allows us to efficiently find dominant eigenvalues/eigenvectors of positive semidefinite matricies) to find a vertex subset of a graph with relatively low expansion. (This material can be found in Chapter 4 of these notes.) We also saw how to compute the eigenvalues and eigenvectors of Cayley graphs of abelian groups. This material can be found in Chapter 5 of these notes.
Lecture 4 - We saw how to construct a family of constant degree expanders using the zig-zag graph product. The material can be found in these notes (note that this is a different source from our usual one).
Lecture 5 - We proved the expander mixing lemma and proved 3 equivalent properties of sequences of dense regular quasirandom graphs. We showed Paley graphs give an example of a sequence of quasirandom graphs. We gave a lower bound on the second absolute eigenvalue of d-regular graphs. Later in the course we may prove that the bound is achieved, i.e. prove the existence of Ramanujan graphs. There are no online notes for this lecture, but here are scanned copies of my notes.
Lecture 6 - We introduced Shannon capacity and the Lovasz theta function of a graph. Our main goal was to determine the Shannon capacity of the 5-cycle, proving various inequalities between parameters along the way. The material for this lecture can be found in Chapter 28 of these notes.
Lecture 7 - The linear algebra method and the polynomial method. Covered: 13.11-13.13, 16.1-16.3 and 16.5-6. from Jukna's book.
Lecture 8 - The solution to the cap set problem by Ellenberg and Gijswijt. See these notes.
Lecture 9 - Hilbert's Nullstellensatz with combinatorial applications. See Section 2 in the lecture notes. Started with Alon's combinatorial Nullstellensatz, 16.7 in Jukna's book.
Lecture 10 - Covered Alon's Combinatorial Nullstellensatz with some applications;16.8, and 16.10-14 in Jukna's book.
Lecture 11 - We proved that a collection of real rooted polynomials with positive leading coefficients has a common interlacer if and only if they are pairwise compatible, if and only if all of them are compatible, a result of Chudnovsky and Seymour. See Section 3 in the lecture notes.
Lecture 12 - Using the result of last week, we proved the result of Chudnovsky and Seymour that the independence polynomial of any claw-free graphs has only real roots. I also stated Shearer's theorem about a nonvanishing domain for the independence polynomial of any graph (of bounded degree) and sketched a proof of that. The result of Shearer is not part of the examinable material. See the lecture notes.
Lecture 13 - Covered an overview of this paper of Marcus, Spielman and Srivastava: Marcus, Adam W., Daniel A. Spielman, and Nikhil Srivastava. "Interlacing families I: Bipartite Ramanujan graphs of all degrees." Annals of Mathematics 182.1 (2015): 307-325.
Problem sets
Exercises 1 (to be handed at the beginning of the lecture on Friday 3 March). [Corrections to the exercises, now updated in the link above. In Q1, assume the graph is regular. In Q2 assume n is even and at least 4. For the last part of Q4, the question should ask to find two eigenvalues that are at least 3/2. Question 3(c) is in fact much easier if you ignore the hint.]
Exercises 2 (to be handed at the beginning of the lecture on Friday 17 March or electronically before that time to: b.l.sevenster@uva.nl). Q3d is slightly vague: we will accept any example of a graph for which the inequality fails, although you should be able to construct an infinite family of examples.
Exercises 3 (to be handed in at the beginning of the lecture on Friday 31 March or electronically before that time. Update: in Q4d, you should assume that m is divisible by 4.
Exercises 4 (to be handed in at the beginning of the lecture on Friday 21 April or electronically before that time to: b.l.sevenster@uva.nl and cc'ed to g.regts@uva.nl). The sheet was updated: in Q6, q-1+k should have been q-2+k.
Exercises 5 (to be handed in at the beginning of the lecture on Friday 12 May or electronically before that time to: b.l.sevenster@uva.nl and cc'ed to g.regts@uva.nl).
Exercises 6 (to be handed in at the beginning of the lecture on Friday 02 June or electronically before that time to: b.l.sevenster@uva.nl and cc'ed to g.regts@uva.nl). The sheet was updated: in part 2 (c) is now included that that $x\geq \frac{-1}{4(\Delta-1)}.
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 at least one out of the four following results:
In Viresh's part
-Theorem 2.1 in Viresh's part (Cheeger's inequalities)
-Theorem 5.3 in Viresh's part (Main property of zig-zag product used to construct bounded-degree expanders)
In Guus's part
-Theorem 1.4 in the lecture notes of Guus
-Theorem 16.7 and 16.8 in Jukna's book (this includes exercise 16.5).
You may moreover expect to be asked to provide proofs for some (parts) of the following results:
In Viresh's part
- Theorem 1.8 (basic properties of graph Laplacians
- Proposition 4.2, Theorem 5.1 (exercise), Cor 5.2 (constructing expanders from abelian groups)
- Proposition 5.4 (constructing family of bounded degree expanders from zig-zag product)
- Lemma 6.1 (Expander mixing lemma), Theorem 6.2 (equivalent properties of regular quasirandom graphs), Theorem 6.4 (eigenvalues of strongly regular graphs and quasirandomness of Payley graphs)
- Theorem 7.1 (Shannon capacity of C_5), Theorem 7.3 (alpha(H) <= theta(H)), Lemma 7.4 (theta function multiplicative w.r.t the strong graph product)
In Guus's part
-In Jukna's book: 13.12,13.13,16.1,16.5,16.11,16.12,16.13,16.14
-In Guus' lecture notes: Lemma 1.2, Prop 2.2 and 2.3, Prop 2.6.
We 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. Please note that the results referred to in Viresh's part are numbered according to lectures, not according to the notes of Luca Trevisan.
Exam Solutions