Walk through Combinatorics, Fall 2018
Highly non-parallel roads
When:Mondays, Wednesdays, Fridays 9:30
Where:Posner Hall 147 [map]
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:
- 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.
- 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.
- 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.
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 can be had at my office hours on Wednesdays 1:30–2:30pm and Fridays 2:30–3:30pm in Wean 6202. I am also available by appointment.
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 40% of the grade. There will a mid-term on October 15, which will count for 25% of the grade. There will be a final exam (on December 11 at 5:30pm) which will count for the remaining 35% of the grade.
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 assignment grade will be reduced by 10%.
There will be opportunities for extra credit. Unusually insightful solutions, and other achievements will be appropriately rewarded.
Staying sane and healthy:
This is a graduate course. It is designed to challenge your brain with new and exciting mathematics, not to wear your body down with sleepless nights. Start the assignments early, and get good nutrition and exercise. Pace yourself, for semester is long. If you find yourself falling behind or constantly tired, talk to me.
- August 27: Introduction. Pigeonhole principle. Dirichlet's approximation theorem. Erdős–Szekeres on monotone sequences.
- August 29: Ramsey's theorem. Bounds on the middle binomial coefficient. Stirling's formula (statement). Upper bound on the diagonal Ramsey number. Lower bound on the diagonal Ramsey number (part I). Homework #1
- August 31: Lower bound on the diagonal Ramsey number (part II). Schur's theorem. Probabilistic arguments as counting arguments. Hypergraphs.
- September 3: Labor Day
- September 5: Ramsey's theorem for hypergraphs (vertex and edge versions). Guest lecture by Chris Cox
- September 7: Bounds on hypergraph Ramsey numbers. Radon's lemma in the plane (proof by picture). Erdős–Szekeres on points in convex position (two proofs). Guest lecture by Chris Cox. Homework #2
- September 10: Semirandom constructions of Ramsey graphs. Guest lecture by Po-Shen Loh
- September 12: Bounds on off-diagonal Ramsey numbers. van der Waerden's theorem (part I). Guest lecture by Tom Bohman
- September 14: van der Waerden's theorem (part II).
- September 17: van der Waerden's theorem (part III). Hales–Jewett theorem. Gallai–Witt theorem.
- September 19: Szemerédi's proof of Roth's theorem (part I).
- September 21: Szemerédi's proof of Roth's theorem (part II). Behrend's construction (part I). Homework #3
- September 24: Behrend's construction (part II). Binomial coefficients. Binomial theorem. Changemaking in Fictionland.
- September 26: Monetary reform in Fictionland. Partial fraction decomposition. Generating functions and formal power series.
- September 28: Exponential generating functions. Weak compositions. Solving linear recurrences. Alternating permutations. Homework #4
- October 1: Review of complex analysis (part I): differentiability and contour integration.
- October 3: Review of complex analysis (part II): Cauchy's theorem and Taylor series.
- October 5: Asymptotics for the number of alternating permutations. Better asymptotics for the number of alternating permutations. Homework #5
- October 8: Catalan numbers. Dyck paths. Fibonacci without rabbits.
- October 10: Pringsheim's theorem. Balanced trees (part I).
- October 12: Balanced trees (part II). Domino tilings at large (part I).
- October 15: Test
- October 17: Domino tilings at large (part II). Probability spaces. Expectation. Union bound. Linearity of expectation. Bipartite subgraphs.
- October 19: Mid-semester break
- October 22: Dominating sets. Independent sets. Homework #6
- October 24: Property B, upper bound. Property B, lower bound (part I).
- October 26: Classes cancelled by the president
- October 29: Property B, lower bounds (part II). Markov's inequality. Variance. Chebyshev's inequality.
- October 31: Covariance. Subgraph appearance threshold. Homework #7
- November 2: Distinct sums. Chernoff bound.
- November 5: Existence of codes. Azuma's inequality. Exposure martingales (part I). Notes on exposure martingales.
- November 7: Exposure martingaltes (part II). Concentration of the chromatic number of random graphs.
- November 9: Isoperimetric problem. Mean of chromatic number (part I). Notes on the chromatic number of a random graph
- November 12: Mean of chromatic number (part II).
- November 14: Motivation for the local lemma. Local lemma. Property B in sparse hypergraphs. Homework #8
- November 16: Multicolored translates. Latin transversals (part I).
- November 19: Latin transversals (part II). Motivation for Szemerédi's regularity lemma. Szemerédi's regularity lemma (statement). Notes on the regularity lemma
- November 21: Thanksgiving (part I)
- November 23: Thanksgiving (part II)
- November 26: Szemerédi's regularity lemma (part I).
- November 28: Szemerédi's regularity lemma (part II). Triangle counting lemma. Triangle removal lemma.
- November 30: Another proof of Roth's theorem. Basic idea of additive combinatorics.
- December 3: Ruzsa's triangle inequalities. Notes on sumset inequalities.
- December 5: Ruzsa's covering lemma. Freiman's theorem in bounded torsion groups. Sum-product theorem (statement and applications). Point-line incidences. Graphs without 4-cycles.
- December 7: Szemerédi–Trotter theorem. Crossing lemma.