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 -
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: 17/03. 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 - . Lecture 8 - Lecture 9 - Lecture 10 - Lecture 11 - 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 Exercises 5 Exercises 6 Note that your best 5 out of 6 marks for the exercises will count towards 25% of your final grade. Information about the exam |