# 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
- 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.
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):
| |||||||||||||||||||||||||||

## Worksheets + |
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 |