Math 465: Introduction to Combinatorics
Instructor: Sergey Fomin, 4868 East Hall, 764-6297, [email protected]
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, [email protected].
Course homepage: http://www.math.lsa.umich.edu/~fomin/465f18.html
We are not using Canvas.
Level: undergraduate.
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.
$$
\begin{array}{l}
\left(x_{1}+x_{2}+\cdots+x_{m}+x_{m+1}\right)^{n}=\left(x_{1}+x_{2}+\cdots+\left(x_{m}+x_{m+1}\right)\right)^{n} \
=\sum_{k_{1}+k_{2}+\cdots+k_{m-1}+K=n}\left(k_{1}, k_{2}, \ldots, k_{m-1}, K\right) x_{1}^{k_{1}} x_{2}^{k_{2}} \cdots x_{m-1}^{k_{m-1}}\left(x_{m}+x_{m+1}\right)^{K}
\end{array}
$$
4-5. Generating functions.
6. Stirling numbers.
7-8. Linear recurrences.
9-10. Catalan numbers.
11. Partitions.
12. Inclusion-exclusion.
$$
\begin{aligned}
\left|\bigcup_{i=1}^{n} A_{i}\right| &=\sum_{i=1}^{n}\left|A_{i}\right| \
&-\sum_{1 \leq i<j \leq n}\left|A_{i} \cap A_{j}\right| \
&+\sum_{1 \leq i<j<k \leq n}\left|A_{i} \cap A_{j} \cap A_{k}\right| \
&-\ldots+(-1)^{n-1}\left|\bigcap_{i=1}^{n} A_{i}\right|
\end{aligned}
$$
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.
Let $G=(V, E)$ be a graph and $A, B \subseteq V$. Then the minimum number of vertices separating $A$ from $B$ in $G$ is equal to the maximum number of disjoint $A-B$ paths in $G$.
24. Birkhoff’s theorem. Posets: basic notions.
Birkhoff’s theorem in General Relativity , actually first discovered by Jebsen , states that any local spherically symmetric solution of the vacuum Einstein field equations
$$
R_{\mu \nu}=0
$$
must admit an extra Killing vector, and so be part of the Schwarzschild vacuum metric:
$$
d s^{2}=-\left(1-\frac{2 m}{r}\right)+\frac{d r^{2}}{1-\frac{2 m}{r}}+r^{2}\left(d \vartheta^{2}+\sin ^{2} d \varphi^{2}\right),
$$
where $m$ is a constant representing the mass of the central object (if there is no central mass so that $m=0,$ this is just flat spacetime). If the Killing vector is timelike, the spacetime is locally static, and is asymptotically flat if it extends far enough; the local solution is part of the exterior region $(r>2 m)$ of $(2) .$ If the Killing vector is spacelike, the spacetime is locally spatially homogeneous: it is part of the interior black hole region $(r<2 m)$ of (2), and runs into a singularity if it extends far enough.
25. Chain and antichain decompositions. Sperner’s theorem.
If $A_{1}, A_{2}, \cdots, A_{m}$ are subsets of $N:={1,2, \ldots, n}$
such that $A_{i}$ is not a subset of $A_{j}$ if $i \neq j$
then $m \leq\left(\begin{array}{c}n \ \lfloor n / 2\rfloor\end{array}\right)$
26. Review.
27. Exam 2 (covers Lectures 17-25).
Attendance:
You are expected to attend class. You are responsible for any material and course announcements you miss. There are no make-ups for quizzes or homework.
Math 465 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.
Math 465代写答疑辅导，请认准UpriviateTA
组合数学代写IMath 465 Combinatorics代写graph theory代写离散数学代写请认准UpriviateTA. UpriviateTA为您的留学生涯保驾护航。
更多内容请参阅另外一份实分析代写.
