CMSC CMSC37120-1: Topics in Discrete Mathematics (Arithmetic Combinatorics)

Course description

Autumn11: Tuesday, Thursday 1:30pm-2:50pm (Ry 251)

Office hours. By appointment.

Literature. Most of the material pertained to this course (except for TCS applications) can be found in the monograph [1]. References to more specific sources covering individual topics will be also posted here as we go along.
1. T. Tao and V. H. Vu, Additive Combinatorics, Cambridge University Press, 2009.
2. M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets, Springer-Verlag, 1996.
3. L. Trevisan, Additive Combinatorics in Theoretical Computer Science, 2009.
4. E. Viola, Selected Results in Additive Combinatorics: An Exposition, 2011.
5. G. Petridis, Plunnecke's inequality, 2011.
6. A. Razborov, A Product Theorem in Free Groups, 2007.
7. L. Babai, N. Nisan, M. Szegedy, Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs. J. Comput. Syst. Sci. 45(2): 204-232 (1992).
8. J. Bourgain, Estimation of certain exponential sums arising in complexity theory. Compotes Rendus Mathematique Volume 340, Issue 9, 1 May 2005, Pages 627-631.
9. B. Green and T. Tao, An equivalence between inverse sumset theorems and inverse conjectures for the U^3 norm, 2009.
10. B. Barak, G. Kindler, R. Shaltiel, B. Sudakov and A. Wigderson, Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors, Journal of the ACM, Volume 57, Number 4, April 2010.
11. B. Chazelle, The discrepancy method, Cambridge University Press, 2002.
12. Lecture Notes of my Course on Quantum Computing.
13. L. Lovasz and B. Szegedy, Limits of dense graph sequences, J. Comb. Theory B 96 (2006), 933-957.
14. M. Braverman, K. Makarychev, Y. Makarychev, A. Naor, The Grothendieck constant is strictly smaller than Krivine's bound, 2011.
15. I. Ruzsa and A. Szemeredi, Triple systems with no six points carrying three triangles, Colloq. Math. Soc. J. Bolyai 18 (1978), 939-945.
16. P. Keevash, Hypergraph Turan Problems, Surveys in Combinatorics, 2011.
17. N. Alon, E. Fisher, M. Krivelevich and M. Szegedy, Efficient Testing of large Graphs, Combinatorica, 20(4), 2000, 451-476.
18. W.T. Gowers, Quasirandomness, counting and regularity for 3-uniform hypergraphs, Combin. Probab. Comput. 15 (1-2) (2006) 143-184.
19. J. Fox, A new proof of the graph removal lemma, Annals of Mathematics 174 (2011) 561-579.
20. B. Green, T. Tao, T. Ziegler, An inverse theorem for the Gowers U^{s+1}[N]-norm, 2010.
21. S. Arora, B. Barak, Computational Complexity, Cambridge University Press, 2009.
22. E. Viola, A. Wigderson, Norms, XOR lemmas, and lower bounds for GF(2) polynomials and multiparty protocols, Theory of Computing, vol. 4, Article 7, pp. 137-168, 2008.
23. S. Lovett, R. Meshulam, A. Samorodnitsky, Inverse conjecture for the Gowers norm is false, STOC 2008.
24. B. Green, T. Tao, The distribution of polynomials over finite fields, with applications to the Gowers norms, 2007.

Progress and references.

First week: administrative and introduction. |2A|<= 2|A|-1 over integers: [2, Theorem 1.2]. e-transforms and their properties: [1, Lemma 5.2]. Cauchy-Davenport theorem: [1, Theorem 5.4]. Vosper's theorem (without proof): [1, Theorem 5.9]. Kneser's theorem: [1, Theorem 5.5]. Note that while they assume on page 201 that e=0, we did not make that assumption. The place that was given without proof corresponds to the first line on page 202, you should parse their inequality (5.3). The problem with the place that I did not understand turned out subtler than I expected. I will explain in class the next time we meet (if you want to do it yourself, read carefully the paragraph with equation (5.5) in it).

Third week: proof of Kneser's theorem cntd. Freiman's theorem: discussion. Doubling constants and multi-dimensional arithmetic progressions, proper progressions. "Properization" (without proof): [1, Theorem 3.40]. Freiman's theorem (statement): [2, Theorem 8.1]. Plunnecke-Ruzsa estimates: [2, Theorem 7.8] or [1, Corollary 6.29], our proof will follow a course intermediate between [2, Section 7] and [1, Section 6.5]. Magnification ratio: [1, Definition 6.23]. Plunnecke inequality: [2, Theorem 7.4] or [1, Theorem 6.27]. Ruzsa triangle inequality: [2, Lemma 7.4]. The correct reduction of Plunnecke-Rusza estimates to the Plunnecke inequality (what I tried to do in class seems to be insufficient due to the uniformity issue we discussed) is in the proof of [2, Theorem 7.8] on page 219. Plunnecke graphs (that we called "commutative'' in class): [2, Section 7.1] or [1, Definition 6.25].

Fourth week: proof of Plunnecke inequality cntd. Menger's theorem can be found in any textbook on graph theory or in [2, Section 7.4]. Multiplicativity of magnification ratios (hard direction): [2, Section 7.3]. Just to give you some idea how lucky we are to have this result here, an analogous statement for independence number is false, and attempts to understand its behavior lead to deep things like Shannon capacity and Lovasz theta function with many important problems still open. Guest lecture: Quadratic pseudorandomness and decomposition theorems for bounded functions by Julia Wolf.
Fifth week: proof of Plunnecke inequality finished. New proof of the Plunnecke inequality can be found in [5], and if you are interested only in it's consequences (that is, Plunnecke-Rusza estimates), you can read this strikingly simple argument at Tim Gowers's blog. Statistical version of the Plunnecke-Rusza estimates is from [6, Section 6] (if you read that paper, notice that we had to switch the roles of $A$ and $B$ to make it consistent with the other material). The repeated Cauchy-Shwarz argument was used countlessly (well, almost) many times in Combinatorics and TCS. Two analogies that immediately come to mind are the lower bound for multi-party communication complexity [7] and Bourgain's correlation bound [8]. The example showing that the doubling constant is irrelevant in the non-commutative case can be also found in [6], and the main result there (see also the preceding research cited therein) says that the tripling constant, on the contrary, is very relevant. Balog-Szemeredi-Gowers theorem (without proof): [1, Theorem 2.31]. Our discussion of Freiman's main theorem and it's major drawback is mostly freelance, but Freiman's dimension lemma can be found in [1, Lemma 5.13] and Freiman's $2^n$ theorem is [1, Theorem 5.20]. Our variant of the polynomial Freiman-Rusza conjecture for integers is a (significantly) more aggressive version of [9, Conjecture 1.6]. Our account of Erdos-Szemeredy's conjecture ([1, Conjecture 8.13]) and related topics follows [1] rather closely. Elekes's bound: [1, Theorem 8.14]. Szemeredi-Trotter theorem: [1, Theorem 8.3]. Lower bounds on the crossing number: [1, Theorem 8.1].

Sixth week: Szemeredi-Trotter theorem and bounds on the crossing number cntd. Bourgain-Katz-Tao theorem (sum-product estimates in finite fields), with a skecth of proof: [1, Theorem 2.55]. The quotient set: [1, Definition 2.49]. The "magic" place where the Plunnecke-Rusza type stuff suddenly turns into a crucial piece of structural information is [1, Corollary 2.52]. Applications to pseudo-randomness and constructive Ramsey theorems were worked out in a series of papers; the latest of them seems to be [10] that also contains all relevant references. Szemeredi's theorem uses up two sections in [1]: 11 and 12. For the terminological confusion surrounding the term "Erdos-Turan conjecture" see e.g. Wikipedia article. Triangle Removal Lmma is [1, Lemma 10.46]. Our direct (i.e., bypassing [1, Proposition 10.45]) reduction of the case $k=3$ to this statement seems to be a part of folklore. Our definition of $\epsilon$-regular (known in other circles as quasi-random) bipartite graphs is slightly different from [1, Definition 10.41] but is equivalent to the latter up to a polynomial increase in $\epsilon$. A good general reading on discrepancy is [11], and for specific applications in communication complexity (quantum and classical) you can consult [12, Section 7]. The primary source of information on graph limits is Laszlo Lovasz's page. The seminal paper on the subject is [13], and [13, Section 4.1] corresponds to our discussion of different norms (although the cut-norm is still called "rectangular" there).

Seventh week (long): The latest paper on Grothendieck inequality is [14]. Szemeredi's Regularity Lemma (without proof): [1, Lemma 10.42], a proof can be found in any advanced book on graph theory. The proof of Triangle Removal Lemma (as well as much of the following material) is from the seminal paper [15]. A good modern survey on hypergraph Turan problems is [16]. The induced matchings theorem is [1, Proposition 10.45], and it's "elementary" inference from the Triangle Removal Lemma is [1, Exercise 10.6.3]. (6,3)-theorem: [1, Exercise 10.6.2]. Induced removal lemmas and property testing: [17]. Wikipedia article is a very good source of information on the current state of Aanderaa-Karp-Rosenberg conjecture (both deterministic and probabilistic versions). An accessible reading on hypergraph regularity, quasi-randomness etc. is [18]. Simplex removal lemma: [1, Theorem 11.27]. Numerical bounds for Szemeredi's regularity lemma, with references, can be found in Wikipedia article. The recent paper [19] makes some progress on improving the bounds in removal lemmas. As for Szemeredi's theorem (for k=3) itself, known numerical bounds on $r_3(N)$ are presented mostly in [1, Section 10.4]. Behrend's example is [1, Exercise 10.1.4]. Our sketch of the proof of the general version of Szemeredi's theorem follows Gowers's argument [1, Sections 11.1-11.4] rather closely. We defined Gowers uniformity norm via the expanded formula [1, (11.1)] and deduced the inductive definition from it; they do it another way around. Generalized von Neumann theorem: [1, Lemma 11.4].

Eighth week (long): Generalized von Neumann theorem cntd. Gowers inner product, Gowers-Cauchy-Shwarz inequality and Gowers triangle inequality: [1, pages 419-420]. The general strategy of the proof of Szemeredi's theorem is discussed throughout [1, Sections 11.1-11.4]. Density Increment Theorem (without proof): [1, Proposition 11.10]. Warm-up: characterization of $U^2$-norm via Fourier coefficients: [1, (11.3)]. Higher-degree characters (axiomatic treatment): [1, Definition 11.5]. The relation between $u^d$ and $U^d$, easy direction: [1, page 426]. Furstenberg-Weiss example (just mentioned): [1, Proposition 11.8]. Inverse Theorem for $U^3$ (without proof): [1, Theorem 11.9]. Inverse Theorem for higher $d$ (just mentioned): [20]. "Erdos-Turan conjecture", analytical form: Wikipedia article. Grren-Tao theorem on arithmetic progressions in primes: general set-up. Guest lecture: Decomposition Theorems in Combinatorics and Complexity by M. Tulsiani.

Nineth week (short): Tulsiani's lecture cntd. Multi-party communication complexity was introduced in [7], see also [21, Section 13.3]. For the original (Yao's) XOR Lemma see [21, Section 19.1].

Tenth week: XOR Lemma in multi-party communication complexity: [22, Section 3]. Counterexamples to the inverse conjecture for Gowers norms were independently found in [23,24], our sketch of a proof followed [23]. Project: Kruskal-Katona theorem and its similarities with e-transform (Tatiana Orlova).