# Math 60610 - Basic Discrete Mathematics

## Spring 2017

### Instructor: David Galvin

NOTE: all course information announced here, including the meeting time, is subject to change! The date for the in-class midterm exam is tentative, and also subject to change (though plenty of notice will be given if it does change).

Discrete mathematics is the study of objects that are fundamentally discrete (made up of distinct and separated parts) as opposed to continuous; think ``difference equations/recurrence relations'' as opposed to ``differential equations'', or ``functions defined on a finite set'' as opposed to ``functions defined on the real line''. It 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, ...).

Among the basic objects that are studied in this area are graphs --- sets of points, some pairs of which are joined --- which can be used to model relational structures; hypergraphs --- sets of subsets of a finite set; and permutations --- bijective functions from an ordered set to itself. There are numerous well-developed branches of discrete mathematics, which can be loosely categorized by the sorts of questions they ask and answer. Some examples include:

• enumerative: how many objects are there satisfying a certain property?
• extremal: what is the largest/smallest/densest/sparsest object satisfying a certain property?
• algorithmic: how does one efficiently construct an object satisfying a certain property?
• probabilistic: what does a typical (randomly selected) object look like, given that it satisfies a certain property?
• algebraic: what is the underlying structure of the set of objects satisfying a certain property?
This categorization is far from discrete --- these branches overlap with each other in pleasing and complex ways.

The tools that are used to tackle discrete problems come from all over mathematics. The method of generating function is a powerful tool in enumeration problems, and draws heavily on both real and complex analysis. Algebraic tools, particularly tools from linear algebra, are invaluable in extremal problems. Differential equations are used to track the growth rates of discretely defined families. Methods from probability and information theory are ubiquitous.

This course acts as an introduction to contemporary discrete mathematics. Roughly, the plan is to touch on the following topics:

• Enumeration: basic counting principles (including permutations, combinations, compositions, pigeon-hole principle and inclusion-exclusion), basic counting sequences (such as binomial coefficients, Catalan numbers, Euler numbers, and Stirling and Bell numbers), and recurrence relations and generating functions.
• Structure and existence: Graphs (including trees, connectivity, Euler trails and Hamilton cycles, matching and coloring, Turan-type problems), partially ordered sets and lattices, basic Ramsey theory, error detecting and correcting codes, combinatorial designs, and techniques from probability and linear algebra.
Other topics may be included if time permits.

The course will have no assigned text --- I will provide notes as the semester progresses. The following books well represent the level of the course, and will prove useful as reference resources:

• Stasys Jukna, Extremal combinatorics (with applications to computer science)
• Peter Cameron, Combinatorics (topics, techniques and algorithms)
• J.H. van Lint and R.M. Wilson, A course in Combinatorics
• Miklos Bona, Introduction to enumerative combinatorics

Beyond familiarity with the basics of calculus, real analysis, linear algebra and algebra at the undergraduate level, the course has no real prerequisites other than a willingness to work hard and engage with the material. As such it is appropriate for all graduate students, and junior or senior honors undergraduates. Feel free to contact me if you want to discuss the suitability of the course for you.

Back to the top of the page

Basic information

Back to the top of the page

Assessment

Back to the top of the page

Late assignments

Detailed solutions to homeworks and quizzes will be posted here on their due dates, so late work cannot be accepted. All homework must be done by the due date to receive credit, and all quizzes and exams must be taken at the assigned times. I will not consider requests for homework extensions, or make-up quizzes and/or 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.

Back to the top of the page

Homework

Homework 4 due in class Monday March 27: Section 40, questions 1 through 3, of the lecture notes.

Homework 3 due in class Friday March 3: (Section 15, Q5) AND (Section 22, Q1) AND (Section 25, EITHER Q1 OR Q2) AND (Section 29, EITHER Q1 OR Q2 OR Q3) AND (Section 32, Q1) of the lecture notes.

Homework 2 due in class Wednesday February 15: Section 8, questions 13, 14, 12; Section 11, question 4; Section 13, question 2, and Section 8, question 11, of the lecture notes.

Homework 1 due in class Monday January 30: Section 5, questions 1 through 5, of the lecture notes.

The weekly/biweekly homework is an integral part of the course; it gives you a chance to think more deeply about the material, and to go from seeing (in lectures) to doing. It's also your opportunity to show me that you are engaging with the course topics.

Homework is an essential part of your learning in this course, so please take it very seriously. It is extremely important that you keep up with the homework, as if you do not, you may quickly fall behind in class and find yourself at a disadvantage during exams and quizzes.

You are permitted, in fact encouraged, to work together and help one another with homework, although what you turn in should be written by you. Providing detailed arguments in your homework is important, since learning how to write mathematics in a rigorous and yet concise and readable way is an essential part of graduate school in mathematics.

Back to the top of the page

Quizzes

Quizzes will be posted here in a single file that will be updated throughout the semester. Quizzes will not be totally problem-oriented, but rather will test basic understanding of definitions and theorems.

Quiz solutions will also be posted here.

Back to the top of the page

Exams

The midterm exam was held on Wednesday March 22, in class. The exam, together with solutions, is incorporated into the class lecture notes. The final is take-home, and is due back on Thursday, May 11 by 6.15pm.

Back to the top of the page

Lecture notes

Back to the top of the page

Conduct

Honor code: This hardly needs to be said, but there's no harm in it: I expect all students to abide by the university's 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.

Class conduct: The lecture room should be a place where you should feel free to engage in lively discussion about the course topic; don't be shy! But non course related interruptions should be kept to a minimum. In particular, you should turn off or switch to silent all phones, etc., before the start of class. If for some good reason you need to have your phone on during class, please mention it to me in advance.

Back to the top of the page