Walk through Combinatorics, Fall 2014

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 three 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.

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]

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

More fun:

More fun can be had at my office hours on Mondays 2:30–3:30pm and Thursdays 10:30–11:30am 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 25: Introduction. Dirichlet's approximation theorem.
• August 27: Erdős–Szekeres on monotone sequences. Ramsey's theorem. Upper bounds on Ramsey numbers. Schur's theorem.
• August 29: Lower bounds on the Ramsey numbers. About bounds on the Ramsey function, and probabilistic arguments. Hypergraphs. Ramsey's theorem for hypergraphs.
• September 1: Labor Day
• September 3: No class
• September 5: Ramsey's theorem for hypergraphs (edge version). Erdős–Szekeres on points in convex position. Guest lecture by Tom Bohman
• September 8: Stepping-up lemma. Zorn's lemma. Statement of compactness principle. Homework #1
• September 10: Proof of compactness principle. Infinite Ramsey theorem. Chromatic number of the plane. Notes on the compactness principle.
• September 12: van der Waerden's theorem (part I).
• September 15: van der Waerden's theorem (part II).
• September 17: Statement of Hales–Jewett theorem. Tic-tac-toe. Gallai's theorem. Cubes in sets of positive density (statement).
• September 19: Cubes in sets of positive density. Szemerédi's proof of Roth's theorem (part I).
• September 22: Szemerédi's proof of Roth's theorem (part II). Homework #2
• September 24: Linearity of expectation. Bipartite subgraphs. LYM inequality.
• September 26: Sum-free subsets. Two expectations problems. Alterations. Independent sets.
• September 28: Large girth and large chromatic number. Guest lecture by Tom Bohman
• October 1: Property B. Guest lecture by Tom Bohman
• October 3: Variance and Chebyshev's inequality. Concentration of binomial distribution. Subgraph appearance threshold.
• October 6: Distinct sums. Motivation for the local lemma. Lovász local lemma.
• October 8: Property B in sparse hypergraphs. Colorful colorings of the real line. Decomposing packings (part I). Homework #3
• October 10: Decomposing packings (part II). 𝛃-frugal colorings.
• October 13: Chernoff's inequality. Martingales. Edge- and vertex-exposure martingales. Azuma's inequality (statement).
• October 15: Azuma's inequality (proof). General exposure martingales. Lipschitz functions. Concentration of the chromatic number. Notes on exposure martingales.
• October 17: Mid-semester break
• October 20: Mean of chromatic number (part I). Notes on the chromatic number of a random graph
• October 22: Mean of chromatic number (part II). Isoperimetric problem in the plane. Isoperimetric problem in the Hamming cube. Homework #4
• October 24: Szemerédi's regularity lemma (part I).Notes on the regularity lemma
• October 27: Szemerédi's regularity lemma (part II).
• October 29: Triangle removal lemma. Another proof of Roth's theorem.
• October 31: Behrend's construction. Basic counting.
• November 3: Binomial theorem. Changemaking in Fictionland. Monetary reform in Fictionland (part I).
• November 5: Monetary reform in Fictionland (part II). Ordinary and exponential generating functions. Compositions (bijection). Homework #5
• November 7: Compositions (generating functions). Alternating permutations.
• November 10: Complex analysis review. Holomorphic functions. Integrals. Cauchy's theorem.
• November 12: Consequences of Cauchy's theorem. Catalan numbers.
• November 14: Dyck paths. Bijection for Catalan numbers. Fibonacci without rabbits.
• November 17: Generating functions as homomorphisms. Pringsheim's theorem.
• November 19: Balanced (2,3)-trees. Domino tilings at large (part I). Homework #6
• November 21: Domino tilings at large (part II).
• November 24: Domino tilings at large (part III). Motivation for additive combinatorics. Structure of sets with small doubling (informal). Guest appearance by Alan Frieze
• December 1: Sum-product estimates via crossing numbers (part I).
• December 3: Sum-product estimates via crossing numbers (part II).
• December 5: Basic inequalities of additive combinatorics. Notes on sumset inequalities.