# 21-228: Discrete Mathematics (Spring 2023)

## Po-Shen Loh

Last updated 18 Jan 2023.

## Location

• Lecture meets Mon/Wed/Fri 1:00–1:50pm in Doherty A302.
• Instructor office hours are Mon Noon–1pm and Wed 2–3pm, in Wean 6208.

• Teaching assistants: Ting-Wei Chao Khunpob Sereesuchart, and Helen Yang.
• TA office hours: See Canvas.

## Course Description

Combinatorics, which concerns the study of discrete structures such as sets and networks, is as ancient as humanity's ability to count. Yet although in the beginning, combinatorial problems were solved by pure ingenuity, today that alone is not enough. A rich variety of powerful methods have been developed, often drawing inspiration from other fields such as probability, analysis, algorithms, and even algebra and topology.

This course provides a general introduction to this beautiful subject. Students will learn both classical methods for clever counting, as well as how to apply more modern methods to analyze recursions and sequences. Students will also learn fundamental techniques in graph theory. Throughout the course, students will encounter novel challenges that blur the lines between combinatorics and other subjects, such as number theory, probability, and geometry, so that they develop the skills to creatively combine seeming disparate areas of mathematics.

This course is structured around challenge. Lecture topics are hand-picked to reflect the rather advanced ability level of the general CMU student, and consequently, much of the curriculum sequence is original. Homework and exam problems are particularly difficult, and require creative problem-solving rather than application of learned techniques. To encourage students to truly develop these skills, collaboration is encouraged on homework, and exams (which are non-collaborative) will be open-notes.

The only pre-requisite for the course is one of 21-127 Concepts of Mathematics or 21-128 Mathematical Concepts and Proofs.

## Learning Objectives

Students will learn how to:
• Use classical methods of combinatorial counting to determine exact and asymptotic values.
• Solve a variety of recurrence relations, using linear algebra and generating functions.
• Deduce, conjecture, and prove fundamental results in graph theory.

## Learning Resources

The course roughly follows the order of topics in the well-written book Discrete Mathematics, by L. Lovász, J. Pelikán, and K. Vesztergombi. This book is not required for the class, because the level of CMU students is somewhat beyond. To adjust for the level of students at CMU, a substantial amount of extra material (not in the textbook) is covered in class. Students are encouraged to reference the book for further clarification, as it provides a clear presentation of an alternate perspective on the content discussed in class.

The course grade will be calculated by applying a curve to the following calculation, in which at least 25% of students will receive an A grade:
• Homework: 10%.
• Intermediate exams: 60%.
• Final exam: 30%.
Historically, the cutoff for an A grade has been around 66% of the weighted total points. All exams will be open notes / open book.

## Homework

The only way to learn mathematics is to do mathematics. (Paul Halmos)

In order to encourage students to experiment with the concepts taught in class, homework assignments will be given on alternate weeks. They will be due in class on Fridays, at the beginning of lecture. Each assignment will consist of four to five challenging problems, for which the proof or justification of each answer is more important than actual numerical answer.

Since homework is a learning activity, students are welcome to discuss ideas with each other, although collaboration in the writing stage is not permitted. In other words, please do not look at the actual document that another student is handing in.

## Exams

There will be 3 in-class exams, each with 5 problems, on Fri Feb 10, Fri Mar 17, and Fri Apr 21. There will also be a comprehensive final exam with 8 problems, at a date and time which will be determined by the registrar.

Other make-up exams will be given only in the case of a documented medical excuse, a university-sanctioned absence (e.g., participation in a varsity sporting event), or a family emergency. However, this must be requested before the official start time of each exam.

## Course Policies

Attendance/Participation. Attendance and participation are not part of the course grade, but are strongly encouraged because the curriculum of this class contains many original components.

Academic Integrity and Collaboration. Collaboration as detailed above is permitted only on homework assignments, and not on exams. In the event of academic dishonesty, a score of zero will be assigned, and a communication will be sent to the academic advisor. This policy is motivated by the goal of maintaining a fair environment for all learners.

Late Work. There is no penalty for late homework, except that all homework must be submitted by the final class day of the semester. Any homework submitted after that date receives zero credit. However, students are strongly encouraged to submit homework on time, because this keeps the class in sync for healthy collaboration on homework, and homework is very helpful for exam preparation.

Re-grade Requests. Re-grade requests must be submitted in writing, within one week of receiving the graded assignment. They will be honored, but please note that it is possible for scores to decrease after a re-grade.

Accommodations for students with disabilities. If you have a disability and require accommodations, please contact Catherine Getchell, Director of Disability Resources, 412-268-6121, getchell@cmu.edu. If you have an accommodations letter from the Disability Resources office, I encourage you to discuss your accommodations and needs with me as early in the semester as possible. I will work with you to ensure that accommodations are provided as appropriate.

Statement on Student Wellness. As a student, you may experience a range of challenges that can interfere with learning, such as strained relationships, increased anxiety, substance use, feeling down, difficulty concentrating and/or lack of motivation. These mental health concerns or stressful events may diminish your academic performance and/or reduce your ability to participate in daily activities. CMU services are available, and treatment does work. You can learn more about confidential mental health services available on campus at: http://www.cmu.edu/counseling/. Support is always available (24/7) from Counseling and Psychological Services: 412-268-2922.

## Detailed syllabus

The semester's tentative schedule is detailed below.

 Week Topic Alternate reference Work due Fri Week 1 (Mon Jan 16) Basic counting; induction Chapter 1; Fwd-backward induction Week 2 (Mon Jan 23) Inclusion-exclusion, pigeonhole principle Chapter 2; Dirichlet's approximation theorem (on AoPS) Homework 1 on Wed Week 3 (Mon Jan 30) Homework 2 Week 4 (Mon Feb 6) Binomial coefficients Chapter 3; Lucas' Theorem Exam 1 on Fri Week 5 (Mon Feb 13) Linear algebra and recurrences Chapter 4; Wikipedia, Croot's notes Homework 3 Week 6 (Mon Feb 20) Generating functions Generatingfunctionology (free book), by H. Wilf. Sections 1.1-1.3, 2.1-2.3; notes from MIT's OpenCourseWare Week 7 (Mon Feb 27) More generating functions Homework 4 Week 8 (Mon Mar 13) Introduction to graphs Chapter 7 Exam 2 on Fri Week 9 (Mon Mar 20) Trees Chapter 8 Week 10 (Mon Mar 27) Traveling salesman problem Chapter 9 Homework 5 Week 11 (Mon Apr 3) Matchings Chapter 10 Week 12 (Mon Apr 10) Combinatorial geometry (No class Fri Apr 14) Chapter 11 Homework 6 Week 13 (Mon Apr 17) Ramsey theory Alt refs #1 and #2 from B. Sudakov's Princeton Combinatorics course. Exam 3 on Fri Week 14 (Mon Apr 24) Planar graphs Chapter 12 Homework 7 Final exam TBA Room TBA