Math 511: Introduction to Combinatorics
Spring, 2019
Syllabus

The textbook is van Lint and Wilson, A Course in Combinatorics, 2nd edition.


Main course page | Notes | Presentations | Assignments
My home page

+:       Chapters we will almost definitely cover.
½:      Chapters we will almost definitely partially cover.
0:       Chapters we definitely may or may not cover.
−:       Chapters we will almost definitely not cover.

Annotated Table of Contents

+ 1/23, 25 1. Graphs
+ 1/28 2. Trees (Don't worry about proving the greedy algorithm.)
½ 1/30, 2/1 3. Colorings of graphs and Ramsey's theorem (to before Th. 3.2)
+ 2/1, 4 4. Turán's theorem and extremal graphs
2/4 1a–4a. Problem discussion from Ch. 4, 3, 2, 1
+ 2/6-8 5. Systems of distinct representatives
+ 2/11-13 6. Dilworth's theorem and extremal set theory (See the lemma for Theorem 6.4.)
+ 2/11 6a. Birkhoff polytope – see Beck-Pixton paper
+ 2/18 6b. Sperner generalization from Beck-Zaslavsky paper
½ 2/18-22 7. Flows in networks: to the statement of Th. 7.4; and Prob. 7F
8. De Bruijn sequences
9. The addressing problem for graphs
+ 2/22-3/1 10. The principle of inclusion and exclusion: inversion formulae
3/1 10a. Problem discussion from Ch. 7, 10
11. Permanents
12. The Van der Waerden conjecture
+ 3/4-8 13. Elementary counting: Stirling numbers
+ 3/8-15, 25 14. Recursions and generating functions: to p. 141 (through Catalan)
+ 3/11 App. 2. Formal power series (To see how we do power series without calculus)
+ 3/25 14. Recursions and generating functions: from p. 141 (exponential GF)
3/15, 27 13a-14a. Problem discussion from Ch. 13, 14 (3/27: 13K, 14C, 14G, 14J, 14N)
+ 3/29, 4/1 15. Partitions – that is, partitions of an integer
+ 4/3 16. (0,1)-matrices, to the middle of p. 175.
½ 4/5 17. Latin squares, to statement of Theorem 17.3, also statement of Theorem 17.4.
½ 4/8 18. Hadamard matrices, Reed-Muller codes: to p. 204 top, and p. 208 bottom to p. 210 top.
+ 4/10-22 19. Designs, to p. 234 (See my attempt at organizing the chapter)
4/15 after class 19a. Problem session on Ch. 18-19. Recommended problems on the notes page.
20. Codes and designs
21. Strongly regular graphs and partial geometries
½ 4/24-29 22. Orthogonal Latin squares, to Example 22.2.
+ 4/26 (p.m.) 19/22a. Problem session on Ch. 19, 22. Recommended problems on the notes page.
½ 4/29-5/3 23. Projective and combinatorial geometries, to Problem 23C. (See terminology. See Lemma 23LL.)
½ 5/3 24. Gaussian numbers and q-analogues, to p. 330 top.
½ 5/6-8 25. Lattices and Möbius inversion, to Problem 25C. (See extra Problem 25AA.)
½ 5/8 26. Combinatorial designs and projective geometries, to Example 26.1 and omit proof of Theorem 26.1.
(Purpose: see designs from geometry.)
27. Difference sets and automorphisms
28. Difference sets and the group ring
29. Codes and symmetric designs
½ 5/10 30. Association schemes, to Example 30.6 (don't sweat the details)
31. Algebraic graph theory: eigenvalue techniques
32. Graphs: planarity and duality
33. Graphs: colorings and embeddings
34. Electrical networks and squared squares
35. Pólya theory of counting
36. Baranyai's theorem

Main course page | Notes | Presentations | Assignments
My home page