Math 4707: Intro to Discrete Math
(Introduction to combinatorics and graph theory)
|Sam Hopkins (call me "Sam")
Office: No office this semester!
|Mon-Wed 2:30-4:25pm, on Zoom (see Canvas for link)|
|By appointment, online|
|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.
|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).
|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.
| 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!
|The overall grade for the course will be computed as follows:
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).
| The tentative schedule of assignments is as follows (all HW exercises from the text): |
| 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
|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