COMP 760 (Fall 2012): Additive Combinatorics
- Instructor's contact: See Here
- Lectures: MW 13:05 - 14:25 at MC103 .
- Office Hours: By appointment (hatami at cs mcgill ca)
Course description:
Recommended resources:
The main text for the course is Terence Tao and Van Vu's "Additive Combinatorics", Cambridge Studies in Advanced Mathematics 105, Cambridge University Press.
Other resources:
Prerequisites:
The main prerequisite is mathematical maturity and interest in some of the application fields
(theoretical computer science, combinatorics, number theory).
The students must be comfortable with basic concepts of probability theory such as random variables, linearity of expectations, variance, conditional expectation, and with basic concepts of linear algebra such as orthonormal basis, inner products, linear transformations.
Assignments:
Lectures
- Lecture 1: Tao-Vu Prologue, Lemma 5.3, Theorems 5.4, 5.5, Proposition 2.2/
- Lecture 2: Section 2.2, Corollary 5.6, Section 2.3.
- Lecture 3: Section 2.3 continued, Lemma 2.14, Proposition 2.18.
- Lecture 4: Corollary 2.19, 2.20, Petridis' proof of the Plunnecke-Ruzsa theorem as explained by Tim Gowers. Balog-Szemeredi-Gowers theorem stated (Theorem 2.29).
- Lecture 5: Lemma 2.30, Theorem 2.31, Proof of the Balog-Szemeredi-Gowers theoren started (Lemma 6.19).
- Lecture 6: Corollary 6.20, Proof of the Balog-Szemeredi-Gowers theorem (Page 264). A brief discussion of Sum-Product theorems.
- Lectures 7 and 8: Bourgain-Katz-Tao sum product theorem (Chapter 4 of these notes, and the appendix of this paper).
- Lectures 9 and 10: Basic Fourier Analysis. (See here.)
- Lectures 11 and 12: Roth's theorem in Z_p^n and in Z_n. (Chapter 6 of these notes)
- Lectures 13, 14, 15, 16: Decomposition theorems, Quadratic Fourier analysis (Been Green's notes.) Also the first 16 pages of the paper of Gowers and Wolf is a nice introduction to these topics.
Evaluation
- Assignments: 50%
- Project 45%
- Attending lectures: 5%
Potential Projects
- Triangle Removal Lemma:
- David Conlon's Notes.
- J. Fox, A new proof of the graph removal lemma. Annals of Mathematics 174 (2011), 561-579.
- Testing low-degree polynomials:
- N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn and D. Ron, Testing Reed-Muller codes. IEEE Transactions on Information Theory 51 (2005), 4032--4039.
- Bourgain's 2-Source Extractor:
- J. Bourgain. More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory 1:1-32, 2005.
- Anup Rao. An Exposition of Bourgain's 2-Source Extractor. download.
- Hypergraph Regularity:
- W. T. Gowers, Hypergraph regularity and the multidimensional Szemeredi theorem Annals of Mathematics 166 (2007), 897-946.
- Helfgott's sum-product type result in SL_2(F_p):
- Helfgott, H. A: Growth and generation in SL2(Z/pZ) Annals of Mathematics 167 (2008) 601-623.
- Construction of Expanders via Helfgot's result:
- Bourgain and A. Gamburd: Uniform expansion bounds for Cayley graphs of SL_2(F_p) Annals of Mathematics 167 (2008), 625-642.
- Equiuvalent forms of the Frieman-Rusza conjecture:
- Shachar Lovett. Equivalence of Polynomial Conjectures in Additive Combinatorics. Combinatrorica To appear.
- Croot-Sisask Method:
- E. Croot and O. Sisask, A probabilistic technique for finding almost-periods of convolutions. Geom. Funct. Anal. 20 (2010), 1367-1396.
- quasi-polynomial Freiman-Ruzsa theorem:
- Tom Sanders. On the Bogolyubov-Ruzsa lemma. Anal. PDE. to appear.
- Shachar Lovett. An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem. download
- Transference results via the Hahn-Banach theorem:
- Gowers, W. T. Decompositions, approximate structure, transference, and the Hahn-Banach theorem. Bull. Lond. Math. Soc. 42 (2010), no. 4, 573-606.
- Arithmetic Progressions in Primes:
- Green, Ben; Tao, Terence: The primes contain arbitrarily long arithmetic progressions.Annals of Mathematics 167 (2008), no. 2, 481-547.
- Quasirandom groups.
- Gowers, W. T.: Quasirandom groups. Combin. Probab. Comput. 1 17 (2008), no. 3, 363-387.