Math 4990: UMTYMP Advanced Topics Course

(Combinatorics)

Fall 2020


Instructor: Sam Hopkins (call me "Sam")
Office: No physical office this semester!
E-mail: shopkins@umn.edu 
Classes: Tue: 4-6pm (CDT), on Zoom (see email for link)
Office hours: By appointment, online (via Zoom, email, etc.)
Course content: This is a course in discrete mathematics, including enumerative combinatorics, as well as some graph theory and optimization. We will try to cover as much of the textbook as possible, at the rate of about one chapter a week. There will be an emphasis on reading and writing proofs. When you finish this class, you should be well prepared for upper-division mathematics courses.
Required text: A walk through combinatorics, by Bóna, 3rd edition (although other editions should be ok).
Please contact me if you need help accessing the text.
Course format: Class will be held once a week via Zoom. About half the class time will be spent on lecture, and the other half on working in groups on worksheets related to the material. I will post PDFs of the lecture notes, as well as the worksheets, on this page. The assignments will also be posted to this page. I plan to communicate with the class mostly via messages from Canvas (see below).
Although this will be the main webpage for the course, on the Canvas site you can engage in discussions with me and with other students. We will also use Canvas for submission and return of assignments. You can also check your grades on Canvas. And recordings of the classes will be posted to Canvas.
If you have any suggestions for improving the class, please let me know!
Grading: The overall grade for the course will be computed as follows:
  • Homework = 40% of grade
  • Each of 2 midterms = 20% of grade
  • Final exam = 20% of grade
Homework will be due on Tuesdays before class. There will be 5 homework assignments due usually every other week, but
  • 2 weeks where there will be a week-long take-home midterm exam,
  • a week at the end with a week-long take-home final exam.
Tentative dates for the assignments and exams are in the schedule below.
I encourage collaboration on the homework, as long as each person understands the solutions, writes them up in their own words, and indicates on the homework page their collaborators.
The take-home midterms and final exam are open-book, open-library, open-web, but in contrast to the homework on exams, no collaboration or consultation of human sources is allowed (except you can ask me, the instructor, questions for clarification).
Late assignments will not be accepted. As mentioned, homework submissions will be via Canvas.
Solutions should be well-explained; I won't give credit for an unsupported answer. Complaints about the grading should be brought to me.
If you have a disability which requires accommodation, please let me know (and also contact the Disability Resource Center).

Assignments: The tentative schedule of assignments is as follows. All HW exercises are from the text (3rd edition; check with me if you have another edition):
Assignment Due date Problems
HW #1 Tue., Sept. 22nd
Ch. 1 #: 22, 25, 30
Ch. 2 #: 22, 24, 34
Ch. 3 #: 30, 34, 35, 40, 44, 48
HW #2 Tue., Oct. 6th Ch. 4 #: 35, 36, 39, 40, 41
Ch. 5 #: 26, 27, 31, 32, 35
Midterm #1 Tue., Oct. 13th Here
HW #3 Tue., Oct. 27th Ch. 7 #: 22, 24, 26, 31
Ch. 8 #: 23, 26, 32, 33
Update: instead of 8 #'s 32+33, you can solve this one problem: What is a closed form for the ordinary generating function of the Stirling numbers of the 2nd kind S(n,k) for fixed k, i.e., the function G(x)=sum_{n=0}^{infinity} S(n,k)x^n?
HW #4 Tue., Nov. 10th Ch. 9 #: 24, 25, 28, 30, 39, 44, 45 (assume k >= 2)
Midterm #2 Tue., Nov. 17th Here
HW #5 Tue., Dec. 1st Ch. 11 #: 19, 20, 21, 24 (look at exercises 5 and 7 for definitions/background), 26, 30
Final Exam Tue., Dec. 15th Here

Class worksheets: Worksheet for 9/8 on induction and the pigeonhole principle
Worksheet for 9/15 on poker hand probabilities, and solutions
Worksheet for 9/22 on binomial coefficients and Pascal's triangle
Worksheet for 9/29 on Stirling numbers of the 2nd kind
Worksheet for 10/6 on Stirling numbers of the 1st kind
Worksheet for 10/13 on the Principle of Inclusion-Exclusion
Worksheet for 10/20 on (ordinary) generating functions
Worksheet for 10/27 on Catalan numbers
Worksheet for 11/3 on walks in graphs
Worksheet for 11/10 on trees
Worksheet for 11/17 on coloring
Worksheet for 11/24 on matchings
Worksheet for 12/1 on planar graphs
Worksheet for 12/8 on Ramsey theory

Lecture PDFs: Tuesday, Sept. 8th: here
Tuesday, Sept. 15th: here
Tuesday, Sept. 22nd: here
Tuesday, Sept. 29th: here
Tuesday, Oct. 6th: here
Tuesday, Oct. 13th: here
Tuesday, Oct. 20th: here
Tuesday, Oct. 27th: here
Tuesday, Nov. 3rd: here
Tuesday, Nov. 10th: here
Tuesday, Nov. 17th: here
Tuesday, Nov. 24th: here
Tuesday, Dec. 1st: here
Tuesday, Dec. 8th: here
Tuesday, Dec. 15th: here