CMSC CMSC37120-1: Topics in Discrete Mathematics (Arithmetic Combinatorics)
Course description
Spring16: Tuesday, Thursday 10:30am-11:50am (Ry 277)
-
Office hours. By appointment.
-
Literature. Most of the material pertaining to this course can be found in the monographs [1,2]. References to more specific sources covering individual topics will be also posted here as we make progress.
-
T. Tao and V. H. Vu, Additive Combinatorics, Cambridge University Press, 2009.
-
M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets, Springer-Verlag, 1996.
-
P. Frankl, A new short proof for the Kruskal-Katona theorem, Discrete Mathematics, 48, 1984, 327-329.
-
G. Petridis, New proofs of Plunnecke-type estimates for product sets in groups,
Combinatorica, 32, No 6, 2012, 721-733.
-
A. Razborov, A product theorem in free groups, Annals of Mathematics, 179, No 2, 2014, 405-429.
-
R. O'Donnell, Analysis of Boolean functions, Cambridge University Press, 2014.
-
B. Green, Notes on the polynomial Freiman-Ruzsa conjecture.
-
T. Sanders, On the Bogolubov-Ruzsa lemma, Analysis & PDE, 5(3): 627-655, 2012
-
S. Lovett, An exposition of Sanders' Quasi-Polynomial Freiman-Ruzsa Theorem, Theory of Computing, Graduate Surveys 6 (2015), pp. 1-14
-
M.-C. Chang, Product theorems in SL_2 and SL_3, J. Inst. Math. Jussieu, 7: 1-25, 2008.
-
B. Barak, R, Impagliazzo, A. Wigderson, Extracting randomness using few independent sources, SIAM Journal on Computing, 36(4): 1095-1118, 2006.
-
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, 57(4), April 2010.
-
B. Chazelle, The discrepancy method, Cambridge University Press, 2002.
-
L. Lovasz, Large networks and graph limits, American Mathematical Society, 2012.
-
M. Braverman, K. Makarychev, Y. Makarychev, A. Naor, The Grothendieck constant is strictly smaller than Krivine's bound, Forum of Mathematics, Pi, 2013.
-
I. Ruzsa and A. Szemeredi, Triple systems with no six points carrying three triangles, Colloq. Math. Soc. J. Bolyai 18 (1978), 939-945.
-
J. Fox, A new proof of the graph removal lemma, Annals of Mathematics 174 (2011) 561-579.
-
N. Alon, E. Fisher, M. Krivelevich and M. Szegedy, Efficient Testing of large Graphs, Combinatorica, 20(4), 2000, 451-476.
-
A. Freeze, R. Kannan, The Regularity Lemmas and Approximation Schemes for Dense Problems, 1996.
-
B. Green, T. Tao, T. Ziegler, An inverse theorem for the Gowers U^{s+1}[N]-norm, Annals of Mathematics, 176, 2012, 1231-1372.
-
B. Green, T. Tao, The primes contain arbitrarily long arithmetic progressions, Annals of Mathematics, 167, 2008, 481-547.
-
D. Conlon, J. Fox and Y. Zhao, The Green-Tao theorem: an exposition,
EMS Surveys in Mathematical Sciences, 1, 2014, 249-282.
-
A. Razborov, What is a Flag Algebra?, Notices of the American Mathematical Society, 60(10), 2013, 1324-1327.
-
Ongoing syllabus and additional references. This section will be updated regularly, normally at the end of
a week.
-
First week: administrative and introduction. |A+B|>= |A|+|B|-1 over integers: [1, Lemma 5.3]. Inverse result: [1, Proposition 5.8]. Cauchy-Davenport theorem: [1, Theorem 5.4].
Inverse result: Vosper's theorem (without proof), [1, Theorem 5.9]. e-transforms and their properties: [1, Lemma 5.2]. Kneser's theorem: [1, Theorem 5.5]. As I said in class,
we do not work under the assumption e=0 (and when $e$ gets resurrected on page 202, we use the letter $h$ for it).
-
Second week: Proof of Kneser's theorem cntd. Frankl's proof of Kruskal-Katona Theorem: [3]. (3k-3) theorem (partial proof): [1, Theorem 5.11]. Freiman's theorem: discussion.
Doubling constants and multi-dimensional arithmetic progressions, proper progressions. "Properization" (without proof): [1, Theorem 3.40]. Freiman's theorem (statements):
torsion-free case [1, Theorem 5.32], torsion case [1, Theorem 5.27]. Freiman's isomororphisms: [1, Section 5.3]. Plunnecke-Ruzsa estimates (statement): [1, Corollary 6.29];
for the old-fashioned proof that we do not do this year read [1, Section 6.5] or [2, Section 7]. Ruzsa triangle inequality: [1, Lemma 2.6]. Ruzsa distance: [1, Definition 2.5].
-
Third week: Plunnecke-Rusza estimates: [4] or Tim Gowers's blog. Reduction to $Z_N$
via a Freiman isomorphism: [1, Lemma 5.26]. Collision numbers (aka additive aenergy): [1, Definition 2.8]. Statistical version of Plunnecke-Ruzsa estimates (without proof):
[5, Section 6]. For general Pontryagin duality see e.g. Wikipedia article, but we will try to use Fourier analysis
only on finite groups. Slightly different notational systems for it can be found in [1, Section 4.1] (close to ours, the main difference is that we prefer to call the torus by its
given name) and [6] (works perfectly well in characteristic 2, sort of standard in Theory). Both sources also contain all basic facts we reviewed. Important characters:
[1, Definition 4.34]. Bohr sets ("boxes"): [1, Section 4.4]. Bohr sets in sumsets of sets with large collision number: [1, Proposition 4.39]. As I said, if you want a better
dependence on $K,\mu$, you will have to do significantly more work, a good sample of which is [1, Lemma 4.36].
-
Fourth week: A crash course on the geometry of numbers: [1, Sections 3.1.1, 3.1.2, 3.5]. Minkowski's second theorem: [1, Theorem 3.30]. Bohr sets contain large generalized arithmetic progressions: [1, Proposition 4.23].
Rusza's covering lemma: [1, Lemma 2.14]. Proof of Freiman's theorem in the torsion-free case completed. For an extended discussion of the Polynomial Freiman-Rusza conjecture see e.g. [7]. Sanders's result confirming the
quasi-polynomial version of it: [8]. Our proof sketch (for $\mathbb Z_2^n$) followed the exposition in [9]. Balog-Szemeredi-Gowers theorem: [1, Theorems 2.31, 2.29] (so far we have done reduction from the latter to the former which is [1, Lemma 2.30]).
-
Fifth week: Proof of Balog-Szemeredi-Gowers cntd. Non-commutative analogues: [1, Section 2.7]; a partial generalization of the Plunnecke-Rusza theory: [1, Proposition 2.40]. Balog-Szemeredi-Gowers
can actually be extended to the non-Abelian case: [1, Theorem 2.44]. Inverse theorems (without proofs): in $SL_2(\mathbb C)$ [10] and in the free group [5]. 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]. Bourgain-Katz-Tao theorem (sum-product estimates in finite fields), with a skecth of proof: [1, Theorem 2.55]. Katz-Tao lemma: [1, Lemma 2.53].
-
Sixth week: Bourgain-Katz-Tao theorem cntd. 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 starting with [11]; the latest of them seems to be [12] that also contains all relevant references. Szemeredi's theorem and its different proofs is covered in two sections of [1]: Section 11 and Section 12. Behrend's example: [1, Exercise 10.1.4]. Triangle Removal Lemma: [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 certain 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 and its applications is [13]. The standard reference on graph limits (of which quasi-random graphs make a first step) is [14]. The latest paper on Grothendieck inequality is [15]. 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 [16]. More recent proof with a slightly better bound: [17]. (6,3)-theorem: [1, Exercise 10.6.2]. The induced matchings theorem: [1, Proposition 10.45].
-
Seventh week: The induced matchings theorem cntd. (6,3)-theorem: [1, Exercise 10.6.2]. Induced removal lemmas and property testing: [18]. Numerical bounds for Szemeredi's regularity lemma, with references, can be found in Wikipedia article. 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; Tao-Vu do it another way around. Generalized von Neumann theorem (statement): [1, Lemma 11.4]. Guest speaker (Tulsiani): Frieze-Kannan weak regularity lemma: [19, Section 5]. Decomposition theorems in higher-order Fourier analysis. Lee's proof of Chang's lemma and Bloom's improvement.
-
Eighth week (short): 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]. Characterization of $U^2$-norm via Fourier coefficients: [1, (11.3)]. Inverse Theorem for $U^3$ (just mentioned): [1, Theorem 11.9]; for the general case see [20].
-
Ninth week: Green-Tao theorem: [21], our exposition followed [22] rather closely. Graph limits [14] and flag algebras [23]. Projects. Sidorenko's conjecture (Coregliano). Furstenberg
correspondence principle and Szemeredi's theorem (Jeronimo).
-
Tenth week: Projects cntd. Very large sumsets in finite fields (Goyal). Algebraic methods in combinatorics (Liu). Strongly regular graphs (Green).
Minkowski's theorems and applications (Biderman).