### Math 465: Introduction to Combinatorics

Winter 2009

Course meets: Tuesday and Thursday 11:40-1:00 in 3088 East Hall.

Instructor: Sergey Fomin, 2858 East Hall, 764-6297, fomin@umich.edu

Office hours: Tuesday and Thursday 1:10-2:30 in 2858 East Hall.

Course homepage: http://www.math.lsa.umich.edu/~fomin/465w09.html

Prerequisites: Linear algebra (Math 214, 217, 256, 286, 296, 417, 419, or equivalent) or permission of instructor.

Student work expected: several problem sets.

Grade will be based on two 1.5-hour midterm exams, 25% each; and 50% homework. Your lowest homework set score will be dropped.

Exams will be held in the same room where the class meets. Tentative dates of exams: March 5 and April 21.

This course will not be graded on a curve, i.e., there are not a set number of each grade to be given out.
Every student with the total score of 90% (resp., 80%, 70%, 60%) is guaranteed the final grade of A (resp., B or higher, C or higher, D or higher).

Synopsis: This course introduces the fundamental notions, techniques, and theorems of enumerative combinatorics and graph theory.

Background: Combinatorics is the study of finite mathematical objects, including their enumeration, structural properties, design, and optimization. Combinatorics plays an increasingly important role in various branches of mathematics and in numerous applications, including computer science, statistics and statistical physics, operations research, bioinformatics, and electrical engineering.

Topics covered (tentative list, subject to change):

• the pigeonhole principle
• inclusion-exclusion
• permutations and combinations
• generating functions
• recurrence relations
• special number sequences
• partially ordered sets
• integer partitions
• matchings and tilings
• graphs and trees
• paths and cycles
• graph coloring
• combinatorial algorithms

Textbook:
R. Brualdi, Introductory combinatorics, 4th edition, Pearson Prentice Hall, 2004. Errata.
Where can I buy this book?

Other introductory textbooks:
E. A. Bender and S. G. Williamson, Foundations of combinatorics with applications, Dover, 2006.
M. Bóna, A walk through combinatorics, 2nd edition, World Scientific, 2006.
V. Bryant, Aspects of combinatorics, Cambridge University Press, 1993.
J. M. Harris, J. L. Hirst, and M. J. Mossinghoff, Combinatorics and graph theory, 2nd edition, Springer, 2008.
R. Merris, Combinatorics, 2nd edition, Wiley, 2003.
G. Polya, R. E. Tarjan, and D. R. Woods, Notes on introductory combinatorics, Birkhäuser, 1990 (draft).

P. J. Cameron, Combinatorics: topics, techniques, algorithms, Cambridge University Press, 1994.
J. H. van Lint and R. M. Wilson, A course in combinatorics, 2nd edition, Cambridge University Press, 2001.
J. Matousek and J. Nesetril, Invitation to discrete mathematics, 2nd edition, Oxford University Press, 2008.

Lectures

1. The pigeonhole principle.
2. The Erdös-Szekeres Theorem. Basic Ramsey Theory.
3. Basic counting principles. Binomial coefficients.
4. Multinomial coefficients. Applications.
5. Pascal triangle. The binomial theorem. Binomial identities.
6. The multinomial theorem. Newton's binomial theorem. Generating functions.
7. Multiplication principle for generating functions. Counting triangulations.
8. Linear recurrences with constant coefficients.
9. Fibonacci numbers. Linear recurrences: the case of multiple roots.
10. Nonhomogeneous linear recurrences.
11. Catalan numbers.
12. Stirling numbers.
13. Inclusion-exclusion principle. Derangements.
14. Permutations with restricted positions.
15. First midterm exam.
16. Basic notions of graph theory. Trees. Independent cycles.
17. Planar graphs. Euler's formula.
18. Eulerian paths and circuits. Hamiltonian cycles.
19. Chromatic number and chromatic polynomial.
20. Spanning trees. The minimal spanning tree problem.
21. The shortest path problem.
22. Flows in networks. The Ford-Fulkerson theorem and algorithm.
23. Menger's theorems. Bipartite networks. Hall's theorem.
24. Reformulations of Hall's theorem. SDR's. Birkhoff's theorem.
25. Partially ordered sets. Chains and antichains. Sperner's theorem.
26. Symmetric chain decompositions.
27. Minimal chain/antichain decompositions. Dilworth's theorem.
28. Second midterm exam.

Homework assignments: (only 5 problems on each problem set are graded)
HW#1, due 01/15: Chapter 2, problems 7, 8, 11, 13, 17, 19(b), 20, 23, 27.
HW#2, due 01/22: Chapter 3, problems 6, 7(f), 9, 14, 22, 26(b), 28(b), 31, 37, 45(c), 46(a).
HW#3, due 01/29: Chapter 5, problems 3, 12, 16, 18, 20, 27, 28, 41; Chapter 7, problems 32, 35.
HW#4, due 02/12: Chapter 7, problems 14, 15, 18, 20, 21, 26, 31, 38, 39.
HW#5, due 02/19: Chapter 8, problems 1, 2, 5, 6, 7, 8, 12(d), 19(b).
HW#6, due 03/24: Chapter 11, problems 12, 20, 30, 31, 34, 44; Chapter 13, problems 19, 23, 26.
HW#7, due 04/02: Chapter 11, problems 75(a), 79, 80(b), 82(b); Chapter 13, problems 11, 14.
HW#8, due 04/09: Chapter 9, problems 11, 12, 14, 16, 27; Chapter 12, problems 24, 25, 26.
HW#9, due 04/16: Chapter 4, problems 35, 47(c), 48; Chapter 5, problems 31, 32, 34, 49.

The first exam covers all material discussed in class by that date.
This roughly corresponds to (parts of) Sections 2.1-2.3, 3.1-3.5, 5.1-5.3, 5.5-5.6, 6.1, 6.3-6.4, 7.1-7.6, 8.1-8.2.

The second exam covers all material discussed in class after the first exam.
This roughly corresponds to (parts of) Sections 4.5, 5.4, 5.7, 9.1, 9.3, 11.1-11.3, 11.5, 11.7, 12.2, 13.1-13.2.

Note that we discuss these sections in a different order, with sometimes different logic of presentation, different examples, etc.