NOTE: all course policies announced here are subject to change up to the first day of semester!

Basic Information

Instructor: Abdul Basit

Office: HAYE 248

Email: abasit@nd.edu

Office Hours: Wednesdays 3:30 pm – 5:00 pm

Meeting Times: MWF 2:00 pm – 2:50 pm, Pasquerilla Center 107

Textbook: Invitation to Discrete Mathematics, 2nd edition by Matoušek and Nešetřil, Oxford University Press, 2008; ISBN-10: 0198570422, ISBN-13: 978-0198570424.

I hope to cover Chapters 2 through 7 and some subset (based on interest) of Chapters 10 through 13. I will provide lecture notes for any topics we cover outside of the textbook.

Course Description

Combinatorics is the study of finite or countable discrete structures. “Discrete” here means that the structures are made up of distinct and separated parts (in contrast to “continuous” structures such as the real line). Combinatorics is an area of mathematics that has been increasing in importance in recent decades, in part because of the advent of digital computers (which operate and store data discretely), and in part because of the recent ubiquity of large discrete networks (social, biological, ecological, …).

Typical objects studied in combinatorics include permutations (arrangements of distinct objects in various different orders), graphs (networks consisting of nodes, some pairs of which are joined), and finite sets and their subsets.

There are many subfields of combinatorics, such as enumerative (e.g., in how many ways can n objects in a row be rearranged, such that no object is returned to its original position?), structural (e.g., when is it possible to travel around a network, visiting each edge once and only once?), and extremal (e.g., what’s the largest number of subsets of a set of size n you can choose, in such a way that any two of them have at least one element in common?). In this course, we will explore each of these aspects of combinatorics, and maybe some more as time permits.

Mathematical preparation: We will make much use of the basic mathematical language of sets and functions, and the techniques of induction and recursion. If you have taken a course such as Math 20630 (Introduction to Reasoning), you will already be familiar with everything we will use. If not, then you will be able to pick it up as the semester progresses.

In either case, I highly recommend going over the Chapter 1 of the course text, which gives a very leisurely introduction both to the problems of discrete mathematics and to the basic language and techniques that the subject uses; it also has some great exercises. If you do not have the text yet, you can find the first chapter here.

Homeworks

• Homework 1 (final update – Jan 27, due Feb 05).
  Solutions are here.

• Homework 2 (final update – Feb 15, due Feb 26).
  Solutions are here.

• Homework 3 (final update – Feb 26, due March 09).
  Solutions are here.

• Homework 4 (final update – March 24, due April 04).
  Solutions are here.

• Homework 5 (final update – April 08, due April 16).
  Solutions are here.

• Homework 6 (final update – April 25, due May 02).
  Solutions are here.

Exams

• The midterm exam was in class on Wednesday, March 07.
  Here is the exam and here are solutions.

• The final exam will be on Monday, May 7 4:15 PM – 6:15 PM in 107 Pasquerilla Center.

Supplementary Material

• Countable vs Uncountable sets. With much more detailed than we talked about in class.
  Here is a chapter from The Book.

• The Binomial Theorem.

• The Twelvefold Way.

• Primes and Bertrand’s postulate.

• P vs NP.

• Lattice Paths and Determinants.

• Extremal Combinatorics I.

• Extremal Combinatorics II.

Assessment

• Homework: Written homework will be assigned roughly every second week (with each homework weighted equally). In total, homework will count for 150 points out of 400. Specific homework policies will be announced with the first homework.

• Midterm: There will be one in-class midterm, planned for Wednesday, March 07. This will count for 100 out of 400 points. Detailed information will be announced closer to the date.

• Final: There will be (cumulative) final exam scheduled for Monday, May 07, 4:15 pm – 6:15 pm. This will count for 150 points out of 400. The location will be announced closer to the date.

Late Assignments

All homework must be done by the due date to receive credit. I will not consider requests for homework extensions, or make-up exams, except in the case of legitimate, university-sanctioned conflicts. It is your responsibility to let me know the full details of these conflicts before they cause you to miss an assignment! Excepting university-sanctioned conflicts, it is your responsibility to be in class for all scheduled lectures.

Honor Code

You have all taken the Honor Code pledge, to not participate in or tolerate academic dishonesty. For this course, that means that although you may (and should) discuss assignments with your colleagues, you must write the final version of each of your assignments on your own; if you use any external sources to assist you (such as other textbooks, computer programmes, etc.), you should cite them clearly; your work on the mid-semester exam and the final exam should be your own; and you will adhere to all announced exam policies.