Walk through Combinatorics, Fall 2012

When:

Mondays, Wednesdays, Fridays 11:30

Where:

Wean Hall 8201

What:

If you ever stumbled upon a mathematical object that is finite and is fun to play with, you must have wandered into the land of combinatorics (also known as discrete mathematics). You might have walked there through one of the many well-trodden roads from logic and computer science, or were yanked through some of the recently-discovered wormholes from number theory or topology. Even if you have not been there, you still might want a guide.

In this course we will explore this land, and learn of paths that connect its different parts. We will focus on four areas:

1. Ramsey theory, where we learn how to find order in the utter chaos. Here the main results are the pigeonhole principle, Ramsey's theorem, theorems of van der Waerden and Hales–Jewett. Much of the time will be devoted to their applications.
2. Enumerative combinatorics, where we learn how to count not only trees, and forests, but also walks, and cycles. Here we encounter clever bijections, Möbius inversion formula, generating functions, Cauchy's theorem as a tool in asymptotic analysis, as well as a multitude of combinatorial objects to count.
3. Probabilistic method, where we learn how use the power of randomness to conjure mathematical objects that are both simple and exotic. Our main helpers will be linearity of expectations, second moment method, alteration tricks, Lovász local lemma, and concentration inequalities. We will also see and use the famed Szemerédi regularity lemma.
4. Arithmetic combinatorics, where we learn how to tame sets of numbers. We will use the sumset inequalities of Plünnecke and Ruzsa, sum-product estimates, as well as theorems of Roth and Balog–Szemerédi–Gowers. If we are lucky, we might even prove Freiman's theorem!

Resources:

Due to the variety of topics, there is no single book that covers everything. Some good written resources covering parts of the course are

• Ramsey theory by Ronald Graham, Bruce Rothschild, and Joel Spencer [library]
• Enumerative combinatorics, volume I by Richard Stanley [library]
• Concrete mathematics by Ronald Graham, Donald Knuth, and Oren Patashnik [library]
• Generatingfunctionology by Herbert Wilf [library] [online]
• Analytic combinatorics by Philippe Flajolet, and Robert Sedgewick [library] [online]
• Probabilistic method by Noga Alon, and Joel Spencer [library]
• Probability Theory and Combinatorial Optimization by Michael Steele for Azuma trickery [video]
• Graph theory by Reinhard Diestel [library] [online]
• Sumsets and structure (chapter) by Imre Ruzsa in Combinatorial number theory and additive group theory [library]
• Additive combinatorics by Terence Tao, and Van Vu [library]

Links to additional resources will be posted as the course progresses.

Student-created resources:

The notes for the class are taken in real-time by JD Nir (text) and Will Macrae (pictures). The notes are like a silent film — they are visually great, but lack the voiceovers. Use them, but refer to the written resources above and to myself if something is unclear.

More fun:

More fun can be had at my office hours on Wednesdays 2:30–3:30pm in Wean 6202 or 6th floor lounge. I am also available by appointment.

Course activities:

Mastery of combinatorics requires practice. Hence, there will be regular homeworks. You are strongly encouraged to do homework individually. Collaboration and use of external sources are permitted, but discouraged, and must be fully acknowledged and cited. Collaboration may involve only discussion; all the writing must be done individually. The homeworks will be returned one week after they are due.

Students are expected to fully participate in the class. Discussions during the lectures are encouraged.

The final grade will be a monotone nondecreasing function of the total homework grade. There will be opportunities for extra credit. Unusually insightful solutions, and other achievements will be appropriately rewarded.

Lectures:

• August 27: Introduction. Dirichlet's approximation theorem. Erdős–Szekeres on monotone sequences.
• August 29: Ramsey's theorem. Schur's theorem. Lower and upper bounds on the Ramsey function.
• August 31: Probabilistic arguments and counting arguments. Hypergraphs. Ramsey's theorem for hypergraphs (vertex version). Erdős–Szekeres on points in convex position.
• September 3: Labor day
• September 5: Ramsey's theorem for hypergraphs (edge version). Homework #1
• September 7: Stepping-up lemma. Compactness principle.
• September 10: Compactness principle (cont'd). Infinite Ramsey theorem. Notes on the compactness principle.
• September 12: van der Waerden's theorem (part I).
• September 14: van der Waerden's theorem (part II).
• September 17: van der Waerden's theorem (part III). Hales–Jewett theorem.
• September 19: Hales–Jewett theorem (cont'd). Gallai's theorem. Cubes in sets of positive density.
• September 21: Szemerédi's proof of Roth's theorem. Homework #2
• September 24: Bookkeeping for Roth's theorem. Binomial coefficients. Stirling numbers of the second kind. Binomial theorem. Changemaking in Fictionland.
• September 26: Changemaking in Fictionland (cont'd). Monetary reform in Fictionland.
• September 28: Generating functions. Compositions. Vandermonde's convolution. Alternating permutations.
• October 1: Alternating permutations. Singularities and asymptotics (part I).
• October 3: Marvels of complex analysis: Cauchy's theorem and relatives.
• October 5: Alternating permutations, revisited. Catalan numbers.
• October 8: Dyck paths. Bijection for Catalan numbers. Fibonacci without rabbits. Homework #3
• October 10: Formal power series. Narrow domino tilings.
• October 12: Balanced trees. Pringsheim's theorem.
• October 15: Balanced trees (cont'd). Domino tilings at large.
• October 17: Domino tilings at large (cont'd).
• October 19: Mid-semester break
• October 22: Linearity of expectation. Bipartite subgraphs. LYM inequality. Homework #4
• October 24: Sum-free subsets. Alterations. Dominating sets. Independent sets.
• October 26: Property B.
• October 29: Property B (cont'd). Large girth and chromatic number.
• October 31: Chebyshev's inequality. Concentration for binomial distribution. Subgraph appearance threshold. Halloween
• November 2: Erdős distinct sum problem. Lovász local lemma.
• November 5: Property B in sparse hypergraphs. Decomposing packings.
• November 7: Lopsided local lemma. Latin transversals. Homework #5
• November 9: Latin transversals (cont'd). Chernoff's inequality.
• November 12: Martingales. Azuma's inequality. Concentration of the chromatic number.
• November 14: General exposure martingales. Random occupancy problem. Mean of the chromatic number (part I).
• November 16: Mean of the chromatic number (part II). Notes on the chromatic number of a random graph.
• November 19: Mean of the chromatic number (part III). Approximate isoperimetric inequality on the hypercube.
• November 21: Thanksgiving (part I)
• November 23: Thanksgiving (part II)
• November 26: Szemerédi's regularity lemma (motivation+statement). Triangle removal lemma (part I).
• November 28: Triangle removal lemma (part II). Another proof of Roth's theorem.
• November 30: Szemerédi's regularity lemma (proof). Notes on the regularity lemma.
• December 3: Behrend's construction. Triangle sumset inequalities.
• December 5: Crossing numbers. Szemerédi–Trotter theorem. Sum-product theorem over the reals.
• December 7: Plünnecke–Ruzsa–Petridis inequalities. Freiman's theorem in a bounded torsion group.