Winter 2010
Course meets: Tuesday and Thursday 11:40-1:00 in 4096 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.
Grader: Daniel Hermes, dhermes@umich.edu.
Course homepage: http://www.math.lsa.umich.edu/~fomin/465w10.html
Level: undergraduate.
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.
Textbook:
R. Brualdi, Introductory combinatorics,
4th
edition, Pearson Prentice Hall, 2004. Errata.
Important: DO NOT BUY THE LATEST 5TH EDITION!
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).
More advanced undergraduate textbooks:
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. Matoušek and J. Nešetril,
Invitation to discrete mathematics,
2nd edition, Oxford University Press, 2008.
Lectures (tentative plan)
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.