Math 4707: Intro to Discrete Math

(Introduction to combinatorics and graph theory)

Spring 2021


Instructor:

 Sam Hopkins (call me "Sam")
Office: No office this semester!
E-mail: shopkins@umn.edu 

Classes:

 Mon-Wed 2:30-4:25pm, on Zoom (see Canvas for link)

Office hours:

 By appointment, online

Prerequisites:

 Math 2243 and either Math 2283 or 3283 (or their equivalent).
Students will be expected to know some calculus and linear algebra, as well as having some familiarity with proof techniques, such as mathematical induction.

Course content:

 This is a course in discrete mathematics, emphasizing both techniques of enumeration (as in Math 5705) as well as graph theory and optimization (as in Math 5707), but with less depth than in either of Math 5705 or 5707.
We plan to cover most of the required text (see below), skipping Chapters 6, 14, 15.
We will also supplement the text with outside material (for instance, worksheets to be done in class-- see below).

Required text:

 Discrete Mathematics: elementary and beyond, by Lovász, Pelikan, and Vesztergombi.
You should be able to access an online version of the text via the UMN library system.

Course format:

 Class will be held twice 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 (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 Wednesdays. You will turn it in on Canvas. 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. Homework solutions should be well-explained-- the grader is told not to give credit for an unsupported answer. Late homework will not be accepted.
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 for clarification).
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 from the text):
Assignment Due date Problems
HW #1 Wed., Feb. 3rd
 1.8: 21, 26, 27
2.5: 4, 5, 8
3.8: 6, 10
HW #2 Wed., Feb. 17th 3.8: 8, 11, 12
4.3: 5, 8, 9(a,b)
5.4: 3, 4(b,c,d)
Note: there's a typo in problem 5.4.4(c,b) where it asks about the probability for S instead of for X.
Midterm #1 Wed., Feb. 24th Here
HW #3 Wed., March 10th In this homework, assume graphs are simple, that is, with no parallel/multiple edges nor self-loops.
In problem 7.3.4, only draw one example of each such graph, up to isomorphism.
7.3: #4, 5, 9, 10
8.5: #2, 3, 7, 11
Note: there's a small typo in problem 8.5.11- it should say "two of its nodes" not "two if its nodes."
HW #4 Wed., March 24th In this homework, again assume graphs are simple, that is, with no parallel/multiple edges nor self-loops.
For 10.4.13, you do not have to do the "second" part (b) about cycles; only do the first two parts, about paths.
9.2: #3, 8
10.4: #5, 6, 13(a,b), 15
Midterm #2 Wed., March 31st Here
HW #5 Wed., April 21st 12.3: #1, 2, 6
Correct the hypotheses of 12.3.6 by also assuming that every vertex has degree 3 (i.e., belongs to 3 edges). And here is a hint for 12.3.2: note that the minimum length of a cycle in a bipartite graph is 4.
13.4: #2, 7, 8
Final Exam Wed., May 5th
(during finals week) 		Here

Worksheets +
supplementary material:

 Worksheet for 1/25 on poker hand probabilities, and solutions (by Drew Armstrong)
Derangements and inclusion-exclusion (by Dennis White)
Worksheet for 1/27 on the Principle of Inclusion-Exclusion
Stirling numbers of the 2nd kind worksheet (by Vic Reiner)
Galton board applet demonstrating the Law of Large Numbers/Central Limit Theorem
Worksheet for 2/3 on binomial coefficients and Pascal's triangle
Generating functions (by Gregg Musiker)
Fibonacci konnakol, percussive Indian classical music (by Manjunath BC)
Worksheet for 2/8 on generating functions
Catalan numbers (by Dennis White)
Worksheet for 2/10 on Catalan numbers
Worksheet for 2/15 on partitions
A really nice graph theory textbook by Bondy and Murty, with more material than our text
Euler Circuits and the Königsberg Bridge Problem (by Janet Barnett)
Some more websites about the existing Königsberg bridges and Hamilton's icosian game
Worksheet for 2/17 on walks and circuits in graphs
Worksheet for 2/22 on trees
Matrices: walks and trees (by Gregg Musiker)
Worksheet for 3/1 on matrices and graphs
Tournaments (by Drew Armstrong)
Worksheet for 3/8 on Minimum Spanning Tree and Traveling Salesman
Worksheet for 3/10 on matchings
Worksheet for 3/15 on finding a matching
An online applet for solving the Max Flow problem using the Ford-Fulkerson algorithm
Worksheet for 3/17 on the Max Flow problem
Gale-Shapley "deferred acceptance" algorithm for school choice (by David Austin)
Talk about how Gale-Shapley was (mis)used for residency matching (by Kevin Williams)
Worksheet for 3/22 on stable matchings
Worksheet for 3/29 on Pick's theorem
Worksheet for 4/12 on graph coloring
Worksheet for 4/19 on planar graphs
Chromatic polynomial (by Dennis White)
Worksheet for 4/28 on the Tutte polynomial

Lecture notes:

 Wednesday, January 20th: here
Monday, January 25th: here
Wednesday, January 27th: here
Monday, February 1st: here
Wednesday, February 3rd: here
Monday, February 8th: here
Wednesday, February 10th: here
Monday, February 15th: here
Wednesday, February 17th: here
Monday, February 22nd: here
Wednesday, February 24th: here
Monday, March 1st: here
Wednesday, March 3rd: here
Monday, March 8th: here
Wednesday, March 10th: here
Monday, March 15th: here
Wednesday, March 17th: here
Monday, March 22nd: here
Wednesday, March 24th: here
Monday, March 29th: here
Wednesday, March 31st: here
Monday, April 5th: No class! Spring Break!
Wednesday, April 7th: No class! Spring Break!
Monday, April 12th: here
Wednesday, April 14th: here
Monday, April 19th: here
Wednesday, April 21st: here
Monday, April 26th: here
Wednesday, April 28th: here
Monday, May 3rd: here