Exploring Combinatorics, Spring 2013

When:

Mondays, Wednesdays, Fridays 9:30

Where:

Margaret Morrison Carnegie Hall, room A14

What:

Combinatorics is an area of mathematics that deals with finite objects. Finite sets, permutations, relations, partitions, graphs, and trees …. These simple combinatorial objects can be used to express beautiful mathematical ideas with little technical work. The ideas that we explore in this course fall into three broad classes:

1. Counting. We will enjoy the transparency of combinatorial bijections, and learn to craft mindless but powerful proofs via generating functions. We will take the idea of counting “all but” to the extreme, and use the resulting principle of inclusion-exclusion to count even the uncountable.
2. Ramsey theory. The pigeonhole principle is the main tool here. Among its many consequences, Ramsey's theorem is singularly important, and we shall see many applications of both.
3. Probabilistic method. A remarkable discovery of XX^th century mathematics is that probability is useful even where order reigns. We shall see the manifestation of this great idea in combinatorics; we will use it to construct objects with most unlikely properties.

On the way, we will learn cheerful miscellanea about graphs, permutations, prime numbers, and rabbits.

Resources:

The main text for the course is Invitation to Discrete Mathematics by Jiří Matoušek and Jaroslav Nešetřil, 2^nd ed. We will occasionally cover topics that are not in the book. Links to additional resources will be posted as the course progresses.

More fun:

More fun can be had at my office hours on Mondays 10:30–11:20am, and Thursdays 11:00–11:50 and 2:30–3:20pm in Wean 6202. I am also available by appointment.

Course activities:

Mastery of combinatorics requires practice. Hence, there will be regular homeworks. Since the homework is for your practice, you are advised to do homework individually. However, collaboration is permitted. Collaboration may involve only discussion, all the writing must be done individually.

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

The homework will count for 25% of the grade. During the semester there will be three tests (on February 6, March 20, and April 24). The lowest test score will be dropped, and the two remaining scores will contribute 25% each. The final exam will take place on May 13 and will count for 25% of the grade.

Lectures:

• January 14: Introduction. Counting odd-sized subsets of an n-set. Homework #1
• January 16: Binomial coefficients, and related bijections. Compositions. Binomial theorem (warm-up).
• January 18: Binomial theorem: semi-combinatorial and algebraic proofs. Stirling numbers of the second kind.
• January 21: First encounter with generating functions: Vandermonde's convolution. Homework #2 No office hours
• January 23: No class
• January 25: Fibonacci numbers.
• January 28: Generalized binomial theorem. Estimates for binomial coefficients.
• January 30: Estimates for harmonic numbers. Overhang in a stack of cards.
• February 1: Changemaking. Partitions (part I). Homework #3
• February 4: Partitions (part II). Generating function for binary trees.
• February 6: Test. Material covered: book sections 3.1 through 3.6 inclusive, and 12.1 through 12.3 inclusive, and all the lectures up to February 1 inclusive.
• February 8: Catalan numbers.
• February 11: Bijection for binary trees and parenthesized expressions. Basic inclusion–exclusion. Area of a spherical triangle. Notes on inclusion–exclusion.
• February 13: General inclusion–exclusion. Probability of two numbers being coprime (part I).
• February 15: Probability of two numbers being coprime (part II). Set families. Sperner's theorem (statement). Homework #4
• February 18: Partial orders. Hasse diagrams. Boolean cubes. Sperner's theorem.
• February 20: Littlewood–Offord theorem. Appetizer for Erdős–Ko–Rado theorem.
• February 22: Erdős–Ko–Rado theorem, part I.
• February 25: Erdős–Ko–Rado theorem, part II. Incidences between points and lines. Number of edges in C₄-free graphs.
• February 27: Number of edges in C₄-free graphs. Cauchy–Schwarz inequality. Erdős–Szekeres theorem on subsequences (statement).
• March 1: Erdős–Szekeres theorem on subsequences. Party of six. Homework #5
• March 4: Clique and anticliques. Ramsey's theorem. Ramsey numbers. Course page illustration explained.
• March 6: Upper bound on Ramsey numbers. Middle binomial coefficient revisited. Lower bound on Ramsey numbers via pigeonhole principle.
• March 8–15: Spring break. No class.
• March 18: Colorings. Counting proofs. Hard Boolean functions.
• March 20: Test. Material covered: book sections 2.1–2.3 (to the extent covered in the lectures), 3.7–3.8, 7.2–7.3, 11.1–11.3, 12.1, 12.4, 12.7, notes on the inclusion–exclusion principle on this page, and all the lectures from February 4 to March 6 inclusive.
• March 22: Two-colorability of set systems. Finite probability spaces. Union bound.
• March 25: Events. Examples of probability spaces. Non-bipartiteness of a random graph. Homework #6
• March 27: Independent events. Construction of paradoxical tournaments.
• March 29: Random variables. Expectation. Indicator random variables. Linearity of expectation. Bipartite subgraphs with many edges.
• April 1: Turán's theorem (examples and statement). Crude version of Turán's theorem.
• April 3: Less crude version of Turán's theorem.
• April 5: Comparisons in QuickSort (part I).
• April 8: Comparisons in QuickSort (part II). Homework #7
• April 10: Markov's inequality. Paranoidal QuickSort. Alterations. Sidon sets.
• April 12: Dominating sets. Better lower bounds on Ramsey numbers.
• April 15: Asymptotics of better lower bounds on Ramsey numbers. Finding several monochromatic triangles.
• April 17: Many monochromatic triangles via double-counting. Goodman's theorem.
• April 19: Spring Carnival
• April 22: Tale from experiment design. Fano plane. Finite projective planes. Order of projective plane. Size of projective plane (statement).Homework #8
• April 24: Test. Material covered: book sections 10.1–10.4, all lectures from March 18 to April 17 inclusive.
• April 26: Size of projective plane. Incidence graph of a projective plane. Dual of a projective plane. Relation to C₄-free graphs.
• April 29: Construction of a projective planes of prime order.
• May 1: Duality in projective planes of prime order. Real projective plane. Latin squares. Orthogonal Latin squares (definition).
• May 3: Orthogonal Latin squares and finite projective planes.
• May 13: Final exam is at 8:30am in Doherty Hall 2302.

Book sections covered (as of May 3): 2.1–2.3, 3.1–3.8, 7.2–7.3, 9.1–9.4, 10.1–10.4, 11.1–11.3, 12.1–12.4, and parts of 2.4 and 12.7.
Some topics were covered at a greater depth in the lecture than in the textbook, and we covered some topics not in the book.