Seminar Course in Additive Combinatorics
Summer 2019, University of Toronto. Supervised by Professor Almut Burchard.
Textbooks & Resources
We are using Tao’s and Vu’s “Additive Combinatorics” as the main textbook and guide to the field. Each chapter is supplemented by more specialized textbooks:
Chapter 1. Alon’s and Spencer’s “The Probabilistic Method.”
Chapter 2. Nathanson’s “Additive Number Theory: Inverse Problems and the Geometry of Sumsets.”
Chapter 3. Lekkerkerker’s and Gruber’s “Geometry of Numbers.”
Week 1 (May 15th)
Introduction to the probabilistic method, first-moment method, second-moment method.
References: Tao & Vu 1.1-1.2; Alon & Spencer Chapters 1,2,4.
My hand-written lecture notes follow the presentation in Tao & Vu, and Alon & Spencer. Suggested exercises adapted from examples in Alon & Spencer.
Week 2 (May 22nd)
The Lovasz Local Lemma, correlation inequalities via the 4-function theorem, the FKG-inequality.
References: Tao & Vu 1.4-1.5; Alon & Spencer Chapters 5,6.
My hand-written lecture notes follow the presentation in Tao & Vu, and Alon & Spencer.
Suggested exercises from Tao & Vu and Alon & Spencer.
Week 3 (May 29th)
Sumsets estimates, the doubling constant, the Ruzsa distance, and the additive energy.
References: Tao & Vu 2.1-2.3.
David Ledvinka’s hand-written lecture notes follow the presentation in Tao & Vu.
Week 4 (June 5th)
Additive bases of different orders, thin bases of order 2, complementary bases, the sunflower lemma.
References: Tao & Vu 1.3, 1.8.
Shuyang Shen’s hand-written lecture notes are based on Tao & Vu.
Suggested exercises from different sources.
Week 5 (June 14th)
Graphs, independent sets and Turan’s theorem, triangle-free graphs and Sidon sets.
References: Tao & Vu 6.1-6.2.
Tanny Libman’s typed lecture notes are based on Tao & Vu, and Ruzsa’s "sum-avoiding subsets” paper.
Suggested exercises from Tao & Vu: 6.1.1, 6.1.2, 6.1.3, 6.1.6, 6.2.1, 6.2.2, 6.2.4.
Week 6 (June 21st)
Finitary combinatorics via infinitary combinatorics + compactness. Ultrafilters, Ramsey Theorem, Erdos-Szekeres Theorem. Van der Waerden’s Theorem via Hales-Jewett Theorem. Topological van der Waerden.
References: Tao & Vu 6.3; Keegan’s online notes.
Keegan Barbosa’s typed lecture notes also include references and suggested exercises.
Week 7 (July 12th)
Introduction to the Geometry of Numbers: Lattices, generalized arithmetic progression, convex bodies, John’s theorem, Brunn-Minkowski inequality.
References: Tao & Vu 3.1-3.4.
Shuyang Shen’s hand-written lecture notes are based on Tao & Vu.
Suggested exercises from Tao & Vu: 3.2.2, 3.2.5, 3.3.1, 3.3.10, 3.4.5, 3.4.9.
Week 8 (July 19th)
Volume packing arguments, Blichfeldt’s lemma, Minkowski’s 1st theorem, Minkowski’s 2nd theorem, applications to number theory.
References: Tao & Vu 3.5.
My hand-written lecture notes follow Tao & Vu.
Weeks 9-10 (August 2nd, August 9th)
Fourier analytic methods: Fourier transform and identities, Hausdorff-Young inequality, convolutions and Young inequality, linear bias, Bohr sets.
Lectures given by Professor Burchard.
References: Tao & Vu 4.1-4.4.
Week 11 (August 16th)
Algebraic methods: the combinatorial nullstellensatz, restricted sumsets, Cauchy-Davenport, Vandermonde determinant, Snevily’s conjecture for finite fields of odd characteristic.
References: Tao & Vu 9.1-9.3.
Tanny Libman’s typed lecture notes are based on Tao & Vu; the proof of Snevily’s conjecture for finite fields is from this paper of Alon. Tanny also pointed out that a later paper of Arsovski resolves the conjecture.
Suggested exercises from a handout of Evan Chen about the combinatorial nullstellensatz.
Week 12 (August 23rd)
Topological dynamics and its applications to additive combinatorics: measure-preserving dynamical systems, topological Van der Waerden, Furstenberg’s multiple recurrence theorem, finite and infinite Szemeredi’s theorem.
References: Tao & Vu 11.5, Yufei Zhao’s notes.
Keegan Barbosa’s typed lecture notes are based on Yufei Zhao’s notes, and also include references and suggested exercises.