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, 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. Assignments will also be posted to this page. I plan to communicate with the class mostly via messages from Canvas.
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, usually due every other week, except for

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. Late assignments will not be accepted. As mentioned, homework submissions will be via Canvas.
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 questions for clarification).
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 notes:

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