Fall 2018
Instructor: Sergey Fomin, 4868 East Hall, 764-6297, fomin@umich.edu
Course meets:
Section 1: Tuesday and Thursday, 1:00-2:20 PM
in 4096 East Hall.
Section 2: Tuesday and Thursday, 2:30-3:50 PM
in 4096 East Hall.
Office hours: Monday and Wednesday, 5:00-6:20 PM, in 4868 East Hall.
Grader: Swaraj Nayegandhi, swaraj@umich.edu.
Course homepage: http://www.math.lsa.umich.edu/~fomin/465f18.html
We are not using Canvas.
Level: undergraduate.
Prerequisites: Math 217 or permission of instructor.
This is a proof-based course: students are expected to understand rigorous mathematical proofs, and supply their own proofs on exams, quizzes, and in homework solutions.
Grade is based on homework (30%), quizzes(10%), and two 1.5-hour exams (30% each).
Homework:
Approximately 10 problem sets.
Homework assignments are due at the start of class.
Homeworks handed in after the lecture has started are considered late,
and penalized.
Homeworks handed in later than the end of class are not accepted.
There are no make-ups for late homework.
The lowest homework score will be dropped in the final calculation.
On each problem set, only 5 problems will be graded.
Quizzes #1 and #2: September 7 and 14, 5:00-5:30 PM, 1360 East Hall. Quiz #3: November 1, in class.
Exams are held in the same room where the class meets.
Each exam is 80 minutes long.
Dates of exams:
October 23 and December 11.
This course will not be graded on a curve, i.e., there are not a set percentage 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).
Students with disabilities:
If you think you need an accommodation for a disability,
please let me know as soon as possible.
In particular, a Verified Individualized Services and Accommodations (VISA)
form must be provided to me at least two weeks prior to the need
for a test/quiz accommodation.
The
Services for Students with Disabilities (SSD) office
(G664 Haven Hall) issues VISA forms.
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: M. Bóna, A Walk Through Combinatorics, 4th edition, World Scientific, 2016.
We will roughly cover the material in Parts II (Enumerative Combinatorics) and III (Graph Theory) of the textbook, together with some other topics. We will not follow the textbook too closely; the lectures and the book will often provide slightly different approaches.
Other textbooks:
R. Brualdi, Introductory combinatorics,
5th edition, Pearson Prentice Hall, 2010.
J. H. van Lint and R. M. Wilson,
A course in combinatorics,
2nd edition, Cambridge University Press, 2001.
J. Matoušek and J. Nešetřil,
Invitation to discrete mathematics,
2nd edition, Oxford University Press, 2008.
Lectures
1. Basic counting principles.
2-3. Binomial and multinomial coefficients.
4-5. Generating functions.
6. Stirling numbers.
7-8. Linear recurrences.
9-10. Catalan numbers.
11. Partitions.
12. Inclusion-exclusion.
13. Review.
14. Exam 1 (covers Lectures 1-12).
15-16. The pigeonhole principle. Ramsey numbers.
17. Graphs: basic notions.
18. Connectedness. Trees and forests. Planarity.
19. Eulerian walks. Hamiltonian cycles.
20-21. Chromatic numbers and chromatic polynomials.
22. Flows in networks.
23. Menger's theorems. Matchings in bipartite graphs.
24. Birkhoff's theorem. Posets: basic notions.
25. Chain and antichain decompositions. Sperner's theorem.
26. Review.
27. Exam 2 (covers Lectures 17-25).
Difficulty:
As this is a 400-level pure math class,
students are expected to make rigorous mathematical
arguments, including producing proofs.
Students will also be held to a high standard of clear and
effective communication;
as a rule of thumb, a hypothetical confused student in the class should
be able to follow your writing.
Classroom equipment:
You may use a laptop or tablet during class; however, if it becomes a
distraction to yourself or others, you may be asked to no longer use it.
Cell phones may not be out during class time.
Classroom behavior:
Come to class on time and do not leave early.
If you have to arrive late or leave early, please let me know in advance.
If you need to work on something for another class,
please do not attend this class.
Academic integrity:
The assignments in this course are individual assignments.
While you may talk to classmates or use other resources to understand
how to approach a problem, you are responsible for answering each problem
on your own.
At the top of your homework, please list
anyone you talked to about the problems (besides myself).
Do not cheat on homework, quizzes or exams.
Consequences for cheating may include failing the course.
Using the internet:
The internet is a tremendous resource for aiding your understanding of the
material we will learn in this class. Don't be afraid to use it like a second textbook! However, be
warned that copying solutions to homework problems from the internet is a breach of academic
integrity.