CMSC 27130/MATH 28130: Honors Discrete Mathematics

• Office hours.

  Alexander Razborov razborov@uchicago.edu Ryerson 360G Monday 2pm-4pm

  Nikhil Patel nvp15@uchicago.edu Crerar 205 Tuesday 4pm-6pm

  Abhijit Mudigonda abhijitm@uchicago.edu Eckhart 127 Friday 4:45pm-6:45pm

• Lecture Notes of a previous version of the course are available, thanks to Yueheng Zhang for the effort! See also partial notes from previous years: 2016 and 2017. Use with care -- every year the content (slightly) evolves, and the content of this year's lectures, as well as approved references that will be appearing below, are the only authoritative sources of information.

• Homeworks. There will be weekly homework assignments due on Wednesday. The first set will be released on October 6 or 7 (and due on October 15). You will be allowed to work together on solving homework problems, but all students must turn in their own independently written solutions. If you work with other people, you must put their names clearly on the write-up -- this is the way to tell apart joint work from plagiarism!
  • Assignment #1, due October 15
  • Assignment #2, due October 22
  • Assignment #3, due October 29
  • Assignment #4, due November 5
  • Assignment #5, due November 12

• Exams. There will be a midterm and a final.

  • Midterm: Friday October 31 9:30am-10:20am
  • Final: Thursday December 11 7:30am-9:30am

• Literature. We will be largely following Discrete Mathematics and Its Applications (8th Edition) by K. Rosen. A significant part of this course, however, will consist of more advanced topics not covered in any single textbook. Relevant literature will be added here (or sometimes in the next syllabus section) as needed. For the starter:

  1. J. Matousek, J. Nesetril, An Invitation to Discrete Mathematics, Oxford University Press, 2009.
  2. L. Lovasz, Combinatorial Problems and Exercises, AMS Chelsea Publishing, 2007.
  3. E. Mendelson, Introduction to Mathematical Logic, CRC Press, 2015.
  4. S. Lang, Algebra, Springer, 3th edition, 2002.
  5. G. Andrews, K. Erickkson, Integer Partitions, Cambridge University Press, 2nd edition, 2010.

  Ongoing syllabus and references.

  • First week: Induction and ordered sets. Introduction. Mathematical Induction: [Rosen, Section 5.1]. Wikipedia articles make a sharp distinction between mathematical induction and all other forms of induction. The sum of the first $n$ integers: [Rozen, Section 5.1.7, Example 1] and of the first $n$ cubes: [Rosen, Sct.5.1, Exercise 4]. Helly's theorem: Wikipedia article. Horse Color Theorem: [Rozen, page 352, Exerc. 49]; see [Rozen, Sct 5.1.8] for another example of the same sort. Strong Induction and Well-Ordering: [Rosen, Sct. 5.2]. Fundamental theorem of arithmetic, existence part [Rosen, Sct. 4.3.2, Theorem 1]. Induction vs. recursion: [Rosen, Sct. 5.3]. Equivalence of different forms of induction: [Rosen, page 365, Exerc. 31, 42, 43]. Linear orderings: [Rosen, Sct. 9.6]. Partially ordered sets [Rosen, Sct. 9.6]. Quasi-orderings: [Rosen, page 669, Exercises 36-38]. Big-O notation: [Rosen, Sct. 3.2.2]. Topological ordering: [Rosen, Sct. 9.6.6], our proof is different. Axiom of Choice: Wikipedia article; surprizingly, the existence of a total extension for an arbitrary poset is not mentioned there. Well-ordered sets: [Rosen, Sct. 9.6, Defintion 4].
  • Second week: Transfinite (aka strong aka well-ordered) induction: [Rosen, Sct. 9.6, Thm. 1]. Lexicographic and co-lexicographic orderings: [Rosen, Sct. 9.6.2]. Ordinal arithmetic: Wikipedia article or any textbook in mathematical logic if you want it at a deeper level. [3, Sct. 4.2] is my favorite. Number Theory. Proof of uniqueness in the Fundamental Theorem of Arithmetic modulo the main lemma: [Rozen, pages 287-288]. Greatest common divisor: [Rosen, Sct. 4.3, Def. 2]. Bezout's Theorem [Rosen, Sct 4.3.8]. Proof of Bezout Theorem via Euclidean Algorithm: [Rosen, Sct 4.3.7, 4.3.8], see specifically Example 18 on page 287. The division algorithm via strong induction (we took it for granted): [Rosen, Example 5 on page 362]. Lame's theorem (with slightly better bound than we did in class): [Rosen, Sct. 5.3.2, Theorem 1]. Polynomials are ubiquitous in math, see the Wikipedia article. Gcd and Euclid's algorithm for univariate polynomials are extensively discussed in another Wikipedia article. Axioms of a commutative ring examplified by $\mathbb Z_m$ (we will talk about the latter next week): [Rosen, Sct. 4.1.5]. For more systematic treatment see any textbook in abstract algebra (I learned my algebra from [4], see Chapter 2 for rings and ideals but let me note that the book is an unmistakeably graduate level).
  • Third week: Principal ideals: another view of Bezout's theorem. Noetherian rings: [4, Chapter 6]; Hilbert's basis theorem (without proof): [4, Sct. 6.2]. Principal ideal domains (those rings where Bezout's theorem holds) and Euclidean domains (those where it can be proved via a suitable generalization of Euclid's algorithm). Equivalence relations: [Rosen, Sct. 9.5]; the partition theorem is [Rosen, Sct. 9.5.4, Thm. 2]. Modular congruences: [Rosen, Sct. 4.1.4], see also [Rosen, Sct. 9.5.2, Example 3] for our running example $\mathbb Z_m$. Factor-rings: [4, Chapter 2]. Invertible elements in $\mathbb Z_m$ [Rosen, Sct. 4.4.2, Theorem 1]: yet another view of Bezout's theorem. Euler's totient function and Euler's Theorem. Fermat's Little Theorem: [Rosen, Sct. 4.4.5]. The RSA scheme is in [Rosen, Sections 4.6.3-4.6.7]; as always, if you need a few more details, see the Wikipedia article, it also contains descriptions of many crypto attacks against this scheme, both successful and alarming. Chinese Remainder Theorem: [Rosen, Sct. 4.4.3]. A constructive proof of uniqueness in this theorem: [Rosen, page 302, Exerc. 29 and 30].
  • Fourth week: Counting. Counting subsets: the proof based on the product rule is [Rosen, Sct. 6.1.2, Example 10], and the inductive proof is [Rosen, Sct. 5.1.7, Example 10]. Functions and related terminology [Rosen, Sct. 2.3]. Cantor-Schroder-Bernstein Theorem (without proof): [Rosen, Sct. 2.5, Theorem 2]. Basic counting principles: [Rosen, Sct. 6.1.2]. Counting functions and injective functions (sometimes also called ``permutations''): [Rosen, Sct. 6.1.2, Examples 6 and 7], [Rosen, Sct. 6.3.2, Example 1]. Binomial coefficients and identitites: [Rosen, Sct. 6.4]. Vandermonde's identity, Pascal's identity and Pascal's triangle: [Rosen, Sct. 6.4]. Binomial Theorem: [Rosen, Sct. 6.4.1]. Inclusion-Exclusion Principle: [Rosen, Sct. 8.5]. Counting surjective functions [Rosen, Sct. 8.6.4]. Stirling numbers of the second kind [Rosen, pages 453-454].
  • Fifth week: Recurrence relation for Stirling numbers: Wikipedia article. The Ball Game (aka Twelvefold Way): [Rosen, Sct. 6.5.5]. Distinguishable balls, distinguishable boxes: multinomial coefficients [Rozen, Sct. 6.5.5, Theorem 4]. Indist. balls, dist. boxes: binomial coefficients again: [Rozen, page 452] (lucky day). Indist. balls, indist. boxes: partitions [Rosen, page 454]. The book [5] is entirely devoted to integer partitions. Pigeon-Hole-Principle. Mirsky's theorem: Wikipedia article. Dilworth's theorem (without proof): Wikipedia article. Erdos-Szekeres theorem, ad hoc proof: [Rosen, Sct. 6.2.3, Thm. 3]. I recommend to read [Rosen, Sct. 6.2] for more beautiful examples of applications of the pigeon-hole principle. Discrete Probability. Historical introduction. Midterm.
  • Sixth week: Probability spaces and events: [Rosen, Sct. 7.2]. Conditional probability: [Rosen, Sct. 7.2.4]. Independent and mutually independent events: [Rosen, Sct. 7.2.5]. The formula of total probability is not explicit in Rosen's book, but it appears in the proof of [Rosen, Sct. 7.3.2, Thm. 1]. Random variables: [Rosen, Sct. 7.2.7] and pushforward distributions: Wikiipedia article. Binomial distribution: [Rosen, Sct. 7.2.6]. Poisson distribution. Geometric distribution: [Rosen, Sct. 7.4.5]. This is a zoo of other important distributions. Expectations and their linearity: [Rosen, Sct. 7.4]. Independent random variables and product of their expectations: [Rosen, Sct. 7.4.6]. Conditional expectations and the law of total expectation: [Rosen, page 518].