Walk through Discrete Mathematics, Fall 2021

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. 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.
3. Algebraic method, where we unleash the power of vector spaces, eigenvalues, and maybe even polynomials on poor combinatorial objects. They will stand no chance.

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]
• Concrete mathematics by Ronald Graham, Donald Knuth, and Oren Patashnik [library]
• Probabilistic method by Noga Alon, and Joel Spencer [library]
• Probability Theory and Combinatorial Optimization by Michael Steele for Azuma trickery [video]
• Linear algebra methods in combinatorics, by László Babai and Péter Frankl, Department of Computer Science, University of Chicago, preliminary version, 1992. [library]
• Thirty-three miniatures (mathematical and algorithmic applications of linear algebra), by Jiří Matoušek, Amer. Math. Soc., 2010. [library] [online]

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

Class format:

The class is expected to be conducted fully in person. Should the university decide to switch to remote instruction, the students should be ready to use Zoom software.

Office hours:

More fun can be had at my office hours on Thursdays 1:30–2:30pm in Wean 6202. 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 30% of the grade. There will a mid-term on October 20, which will count for 30% of the grade. There will be a final exam on December 7 which will count for the remaining 40% 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 andrewid_discr_homeworknumber.tex and andrewid_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:00am 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.

Lectures:

• August 30: Introduction. Pigeonhole principle. Dirichlet's approximation theorem. Ramsey's theorem. Ramsey numbers. Bounds on the middle binomial coefficient. Stirling's formula (statement). Lower bound on the diagonal Ramsey numbers.
• September 1: Probabilistic arguments are counting arguments. Schur triples. Erdős–Szekeres on monotone sequences (via Ramsey and directly). Hypergraphs. Ramsey's theorem for hypergraph (statement + proof idea). Homework #1
• September 3: Two proofs Ramsey's theorem for hypergraphs. Upper bounds on hypergraph Ramsey numbers.
• September 8: Stepping-up lemma. Erdős–Szekeres on sets in convex position. Radon's lemma. Homework #2
• September 10: Infinite Ramsey's theorem. Compactness principle. Notes on the compactness principle
• September 13: Chromatic number of the plane. van der Waerden's theorem (part I).
• September 15: van der Waerden's theorem (part II). Hales–Jewett theorem.
• September 17: Hales–Jewett theorem (part II). Gallai's theorem. Roth's theorem (part I).
• September 20: Roth's theorem (part II).
• September 22: Roth's theorem (part III). Behrend's construction. Homework #3
• September 24: Union bound. Linearity of expectation. Characteristic functions. Union bound as linearity of expectations. Bipartite subgraphs. LYM inequality. Sum-free subsets (part I).
• September 26: Sum-free subsets (part II). Dominating sets. Independent sets. Graphs of large girth and large chromatic (part I).
• September 29: Graphs of large girth and large chromatic (part II). Turán's theorem.
• October 1: Variance. Chebyshev's inequality. Covariance. Subgraph appearance threshold. Distinct sums (part I).
• October 4: Distinct sums (part II). Chernoff's bound. Binomial random variable. Conditional probability. Conditional expectation.
• October 6: Martingales. Azuma's inequaltiy. Exposure martingales. Concentration of chromatic number. Notes on exposure martingales.. Homework #4
• October 8: Chromatic number of a random graph (part I). Notes on the chromatic number of a random graph
• October 11: Chromatic number of a random graph (part II). Discrete isoperimetric inequality (part I).
• October 13: Discrete isoperimetric inequality (part II). Local lemma. Two-colorability of sparse hypergraphs.
• October 15: Multicolored translates. Latin transversals.
• October 18: Szemerédi's regularity lemma (part I). Notes on the regularity lemma
• October 20: Test
• October 22: Szemerédi's regularity lemma (part II). Counting lemma. Homework #5
• October 25: Removal lemma. Corners. Another proof of Roth's theorem.
• October 27: (6,3)-lemma. Erdős–Stone theorem. Counting F-free graphs.
• October 29: (6,3)-lemma (construction). Sharper Erdős–Stone theorem (part I).
• November 1: Sharper Erdős–Stone theorem (part II). Kővári–Sós–Turán theorem. Sharpness of Kővári–Sós–Turán for K_2,2 (detailed), and for K_3,3 (sketch).
• November 3: Unit distances. Szemerédi–Trotter theorem. Crossing lemma. Homework #6
• November 8: Proof of Szemerédi–Trotter theorem. Szemerédi–Trotter theorem is sharp. Sumsets. Sum-product theorem in R (statement).
• November 10: Sum-product theorem in R (proof). Turán's problem for hypergraphs (discussion). L-intersecting families (construction and upper bounds).
• November 12: Explicit Ramsey graphs. Disproof of Borsuk's conjecture.
• November 15: Sunflower lemma. {0,1,3}-intersecting families. Steiner triple systems.
• November 17: Steiner triple systems (part II). Projective geometries. Sauer–Shelah lemma. Homework #7
• November 19: Union and intersection of families of bounded VC-dimension. Veronese embedding. Epsilon-net theorem (part I).
• November 22: Epsilon-net theorem (part II). Shadows of set families. Kruskal–Katona theorem (part I).
• November 29: Uniform cover theorem (part I).
• December 1: Uniform cover theorem (part II). Kruskal–Katona theorem (part II).
• December 3: Erdős–Ko-Rado theorem. Sketch of a proof of the isoperimetric theorem.