Brief overview of the course
This year, we will cover selected topics in discrete harmonic analysis and its applications to additive combinatorics, probabilistic combinatorics, number theory, percolation, random graphs and theoretical computer science. Discrete analogues of Fourier analysis have been critical to many important results in graph theory and additive number theory. In recent years these techniques have led to many sophisticated and deep results in discrete mathematics, probability and related fields, ranging from "sharp thresholds" in random graphs and percolation theory, strong bounds for sum-sets in additive number theory, to the theory of computing and social choice.
The course will take place in Semester I (Sept 2016- Jan 2017) at the campus of UvA. The course is on Thursdays, 14.00-16.45 in room SP G2.13.
Guus Regts and Tobias Müller will each present roughly half of the lectures.
Homework exercises and a written examination (or, depending on the number of participants oral examination). Homework counts for 40% of the final grade.
- O'Donnell, Ryan. Analysis of Boolean functions. Cambridge University Press, 2014
- Lovett, Sachar, An Exposition of Sanders’ Quasi-Polynomial Freiman-Ruzsa Theorem, Theory of computing, graduate survey 6 (2015), pp. 1–14
- Chow YS, Teicher H. Probability theory: independence, interchangeability, martingales. Springer Science & Business Media; 2012 Nov 28.
- Gowers W. Generalizations of Fourier analysis, and how to apply them. Bulletin of the American Mathematical Society. 2016.
- Selected research articles and other sources to be determined during the course.
- 22 September: The first lecture (GR). Introduction to Boolean analysis: Covered Chapter 1 of O' Donnell.
- 29 September: Lecture 2 (GR). Covered 2.1-2.4 of O'Donnel (except Theorem 2.39). Homework. Exercises 1.5, 1.28a, 1.15, 1.16, 2.3, 2.22, 2.33 of O'Donnel. To be handed in on October 13th at the start of the lecture (not by email!).
- 6 October Lecture 3 (TM). Modest recap of part of previous lectures, social choice theory. Proposition 9.27 and its proof, assuming KKL. B-reasonable definition, propositions 9.3, 9.4. Statement of Bonami Lemma, FKN and Friedgut's junta theorem.
- 13 October Lecture 4 (TM). Bonami lemma, Thm 9.7, proof of FKN, (2,4)- and (4/3, 2)-hypercontractivity theorems, Cor. 9.8. Proof of KKL assuming KKL edge-isoperimetric thm.
- 20 October Lecture 5 (TM). Proof of KKL edge-isoperimetric thm (unbiased version, extension to general case is an exercise). Prop 3.31. Thm 9.28. Proof of Friedgut's junta theorem. Discussion of p-biased analysis, and its motivation. Erdös-Rényi random graph model, percolation (critical probabilities, RSW method). Sec 8.4. Homework: hand in your solutions to these exercises (Note: the file has been updated!) at the start of the Nov 17 lecture. (Note only paper copies are allowed, emailed solutions are absolutely not accepted)
- 27 October Lecture 6 (GR). Covered Sections 4 and 5 of the paper by Lovett. Exercises: Extra exercises 2.1, 2.2 and 2.3.
- 3 November Lecture 7 (GR). Covered Section 3, except 3.1 of Lovett, the Level-1 Inequality and lemma 5.31 from O'Donnel together with a version of Hoeffding's bound and Plünnecke's Theorem. Exercises: Extra exercise 2.4 and exercise 5.37 from O'Donnel.
- 10 November Lecture 8 (GR). Covered Section 2.5 of O'Donnel except last half of Page 44. Proof of Khintchine Inequality and the Marcienkiewicz-Zygmund inequality from Section 10.3 in the book of Chow and Teicher. Exercises: 2.49, 2.51(a) and 2.55 from O'Donnel. Homework. Extra exercises (Note: the file has been updated!) 2.2,2.3,2.4 and 2.51(a), 2.55, 5.38 from O'Donnel. With Exercise 5.38 I want you to write out the entire proof of Thm. 5.33 and explicitly fill in all the details (this includes giving a proof of Cor. 5.32). To be handed in at the start of the Dec 1 lecture. (Note only paper copies are allowed, emailed solutions are absolutely not accepted)
- 17 November No class due to illness of lecturer.
- 24 November Lecture 9 (TM) Chapter 8.1, 8.2, 8.3.
- 1 December Lecture 10 (GR) Covered Roth's theorem loosely based on first pages of the paper by Gowers. Homework. Extra exercises 2.5,2.6 and 2.7. To be handed in at latest 22 december at 14:00 hr (by email).
- 8 December Lecture 11 (TM) Statement of Bourgain's sharp threshold theorem. Example of application of Bourgain in percolation. Randomization / symmetrization (def 10.32), prop. 10.34. Def 10.40, fact 10.41. lemma 10.43, case q=4 only, Theorem 10.44 (cases q=4, 4/3 only). Statement of Theorem 10.47, proof of Bourgain assuming 10.47.
- 15 December Lecture 12 (TM) Finished the proof of Bourgain. That is, we did the proof of 10.47, pages 305-308. Please be aware of a typo in Lemma 10.48 : i \in J_x' should be i \not\in J_x'. This recurs in the last line of the proof. Homework (optional, to handed in on or before January 15): 8.10(a), 8.14, 8.19, 10.40, 10.42.
Exam: January 5 14:00-17:00, University of Amsterdam. SP A1.04
Examinable material: everything covered in lectures, and all homework exercises. In general this includes (being able to reproduce) both the statement
and the proof of the results. You may expect at least one exercise on the exam in which we ask you to reproduce the proof of one the results covered in the lecture.
For the following results you need to know the statement only (and you should be able to recognize opportunities to apply it, and to apply it correctly in those cases) : Bourgain's sharp threshold theorem, Sander's theorem (Theorem 1.4 from the paper of Lovett), Lemma 4.2 from Lovett, the Level-1 inequalities, the Marcienkiewicz-Zygmund inequality.
The exam can be found here and the solutions to the exam here.