Walk through Combinatorics, Fall 2015

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. For your own good, you are strongly encouraged to do as much homework as possible individually. Collaboration and use of external sources are permitted, but must be fully acknowledged and cited. All the writing must be done individually. Failure to do so will be treated as cheating. 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 homework will count for 50% of the grade. During the semester there will be two tests (on October 21, and December 4). Each test will count for 25% of the grade. There will be no final exam.

Homework must be submitted in LaTeX via e-mail. I want both the LaTeX file and the PDF that is produced from it. The filenames must be of the form lastname_discr_homeworknumber.tex and lastname_discr_homeworknumber.pdf respectively. Pictures do not have to be typeset; a legible photograph of a hand-drawn picture is acceptable.

The homework must be submitted by 9:30am of the day it is due. For each minute that it is late, the grade will be reduced by 10%.

There will be opportunities for extra credit. Unusually insightful solutions, and other achievements will be appropriately rewarded.

Lectures:

• August 31: Introduction. Dirichlet's approximation theorem. Erdős–Szekeres on monotone sequences.
• September 2: Ramsey's theorem. Upper bounds on Ramsey numbers. Bounds on the middle binomial coefficient. Stirling's formula (statement). Schur's theorem. Homework #1
• September 4: Lower bounds on Ramsey numbers. About bounds on the Ramsey function, and probabilistic arguments. Hypergraphs. Ramsey's theorem for hypergraphs.
• September 7: Labor day
• September 9: Erdős–Szekeres on points in convex position. Order-homogeneous sets in R^d. Ramsey's theorem for hypergraphs (edge version).
• September 11: Stepping-up lemma. Infinite Ramsey theorem. Compactness principle. Notes on the compactness principle. Homework #2
• September 14: Compactness principle (part II). Chromatic number of the plane. van der Waerden's theorem (part I).
• September 16: van der Waerden's theorem (part II). Statement of Hales–Jewett theorem. Tic-tac-toe. Gallai's theorem.
• September 18: Cubes in sets of positive density. Szemerédi's proof of Roth's theorem (part I).
• September 21: Cubes in sets of positive density. Szemerédi's proof of Roth's theorem (part II).
• September 23: Binomial coefficients. Binomial theorem. Changemaking in Fictionland. Monetary reform in Fictionland. Homework #3
• September 25: Generating functions. Exponential generating functions. Weak compositions. Alternating permutations. Review of complex analysis (part I): differentiability and contour integrals.
• September 27: Review of complex analysis (part II): Cauchy's theorem. Consequences of Cauchy's theorem.
• September 30: Taylor's series for holomorphic functions. Asymptotics for alternating permutations.
• October 2: Sharper asymptotics for alternating permutations. Catalan numbers.
• October 5: Dyck paths. Bijection for Catalan numbers. Fibonacci without rabbits.
• October 7: Pringsheim's theorem. Balanced trees (part I). Homework #4
• October 9: Balanced trees (part II). Domino tilings at large (part I).
• October 12: Domino tilings at large (part II). Probability spaces. Random variables. Bipartite subgraphs.
• October 14: LYM inequality. Sum-free subsets.
• October 16: Dominating sets. Independent sets. Graphs of large girth and large chromatic number.
• October 19: Conditional probabilities. Property B.
October 21: Test
• October 23: Mid-semester break
• October 26: Second moment method. Concentration of the binomial distribution. Subgraph appearance threshold. Homework #5
• October 28: Distinct sums problem. Chernoff's inequality. Martingales. Edge-exposure martingales.
• October 30: General exposure martingales. Lipschitz functions. Azuma's inequality. Concentration of the chromatic number. Notes on exposure martingales.
• November 2: Mean of chromatic number (part I). Notes on the chromatic number of a random graph.
• November 4: Mean of chromatic number (part II). Isoperimetric problem (Euclidean motivation).
• November 6: Discrete isoperimetric problem. Motivation for the local lemma. Local lemma.
• November 9: Property B in sparse hypergraphs. Multicolored translates. Latin transversals. Homework #6
• November 11: Szemerédi's regularity lemma (part I).Notes on the regularity lemma
• November 13: Szemerédi's regularity lemma (part II).
• November 16: Triangle counting lemma. Triangle removal lemma. Another proof of Roth's theorem.
• November 18: Behrend's construction. Basic idea of additive combinatorics.
• November 20: Sum product estimates over R. Szemerédi–Trotter theorem.
• November 23: Crossing lemma. Triangle inequalities. Notes on sumset inequalities.
• November 25: Thanksgiving (part I).
• November 27: Thanksgiving (part II).
• November 30: Triangle inequalities (part II). Freiman's theorem in bounded torsion groups.
• December 2: Additive energy. Sum-product theorem in F_p (part I).
• December 4: Test
• December 7: Sum-product theorem in F_p (part II). Balog–Szemerédi–Gowers theorem.
• December 9: Szemerédi–Trotter in finite fields (part I).
• December 11: Szemerédi–Trotter in finite fields (part II).