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).
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.
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
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.
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. Past Exam Paper. This is the exam paper from last year. Please note that the format of the exam last year was slightly different to this year (in particular the list of theorems above was different. Last year we asked for revision of a small number of long proofs and this year we ask revision of a larger number of shorter proofs. The solutions to the exam can be found here.) |