CMSC 27130/MATH 28130: Honors Discrete Mathematics

Autumn 23: Monday, Wednesday, Friday 9:30am-10:20am (Ryerson 276)

Office hours.

Alexander Razborov
razborov@uchicago.edu
Ryerson 360G
Monday 3pm-5pm Cameron Chang
changca@uchicago.edu
Crerar 205
Tuesday 4pm-6pm Theodoros Papamakarios
papamakarios@uchicago.edu
Crerar 205
Friday 4pm-6pm

Lecture Notes of the previous version of the course are available, thanks to Yueheng Zhang for the effort! See also partial notes from previous years: 2016 and 2017.
Homeworks. There will be weekly homework assignments due on Wednesday via Canvas. The first set will be released on October 2 or 3 (and due on October 11). 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!
Exams. There will be a midterm and a final.
- Midterm: Friday October 27 9:30am-10:20am
- Final: Thursday December 7 5:30pm-7:30 pm, Stu 101
Literature. We will partly follow 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, 2004.
6. R. Vershinin, High-Dimensional Probability, Cambridge University Press, 2018.
7. P. Biggs, Strongly Regular Graphs with no Triangles, 2009.
8. D. Cvetkovic, P. Rowlinson, S. Simic, An Introduction to the Theory of Graph Spectra, London Mathematical Society , 2009.
9. P. Keevash, Hypergraph Turan Problems, Surveys in Combinatorics, Cambridge University Press, 2011, 83--140.
10. S. Jukna, Extremal Combinatorics, Springer-Verlag, 2nd edition, 2011.
11. R. Graham, B. Rothschield, J. Spencer, Ramsey Theory, Wiley-Interscience, 2nd edition, 1990.
12. M. Gardner, The Island of Five Colors, in Fantasia Mathematica.
Ongoing syllabus and references will be added here as we are making progress.
- First week (short): Introduction. Mathematical Induction: [Rosen, Section 5.1], I would also like to commend Wikipedia for making 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 [Rosen, Sct. 4.3.2, Theorem 1], existence part. Induction vs. recursion: [Rosen, Sct. 5.3]. Equivalence of different forms of induction: [Rosen, page 365, Exerc. 31, 42, 43].
- Second week: 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]. Linear (or total) quasi-orderings: quasi-orderings + totality. Linear extensions of a poset (without proof): [Rosen, Sct. 9.6.6]. Well-ordered sets: [Rosen, Sct. 9.6, Defintion 4]; transfinite (aka strong aka well-ordered) induction: [Rosen, Sct. 9.6, Thm. 1]. Lexicographic ordering: [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, this is where I learned it when I was your age. 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].
- Third week: Proof of Bezout Theorem via Euclidean Algorithm: [Rosen, Sct 4.3.7, 4.3.8], see specifically Example 18 on page 287. 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$: [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). Noetherian rings: [4, Chapter 6]; Hilbert's basis theorem (without proof): [4, Sct. 6.2]. Principal ideal rings and connections with gcd in general: Wikipedia article, and for algebraic integers in particular: Wikipedia article (you may want to jump to the section ``Class numbers of quadratic fields'' that also contains a sketch of the proof that $Z[\sqrt{-5}]$ is not a ring of principal ideals). 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_n$. Factor-rings: [4, Chapter 2]. For applications of modular arithmetic to cryptography see [Rosen, Sct. 4.6]. Fermat's Little Theorem (without proof): [Rosen, Sct. 4.4.5].
- Fourth week: Chinese Remainder Theorem: [Rosen, Sct. 4.4.3]. Stand-alone proof of uniqueness: [Rosen, page 302, Exerc. 29 and 30]. Injective, surjective and bijective functions: [Rosen, Sct. 2.3]. Cantor-Schroeder-Bernstein Theorem (without proof): [Rosen, Sct. 2.5.3, Thm. 2]. Counting subsets: the inductive proof is in [Rosen, Sct. 5.1.7, Example 10] (notice the nice picture!), the proof based on the product rule: [Rosen, Sct. 6.1.2, Example 10]. 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].
- Fifth week: Counting surjective functions [Rosen, Sct. 8.6.4]. Stirling numbers of the second kind [Rosen, pages 453-454]. For the recurrence relation see 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]. Dist. balls, indist. boxes: Stirling numbers. 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. 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].
- Seventh week: Independent random variables and product of their expectations: [Rosen, Sct. 7.4.6]. Markov's inequality: [Rosen, Exc. 37 on page 519]. Variance and its properties: [Rosen, Sct. 7.4.7]. Chebyshev's inequality: [Rosen, Sct 7.4.8]. Chernoff's bound: [6, Theorem 2.3.1]; more generally, Chapter 2 is a very nice review of many other inequalities with a similar flavor, including Hoeffding. Graphs: [Rosen, Sct. 10.2]. Graph degrees: [Rosen, Sct. 10.2]. Handshaking Theorem: [Rosen, Sct. 10.2, Thm.1]. Erdos-Gallai Theorem (just mentioned). Paths and connectivity: [Rosen, Sct. 10.4]. Path distance: [Rosen, Exerc. 52-53 on page 777].
- Eighth week: Diameter: [Rosen, Exerc. 52-53 on page 777]. Moore bound and Moore graphs. Strongly regular graphs (more information about the triangle-free case can be found in [7]). Adjacency matrices: [Rosen, Sct. 10.3.3]. Counting paths via adjacency matrices: [Rozen, Sct. 10.4.7, Theorem 2]. You can read more about the spectral theory of graphs e.g. in [8]. Graph isomorphisms and graph invariants are discussed in [Rosen, Sct. 10.3]. Basic terminology about subgraphs: [Rosen, Sct. 10.2.7]. Mantel and Turan's theorems. Extremal problems for hypergraphs: [9]. An excellent (albeit somewhat thin on graphs) text on extremal combinatorics in general: [10]. Bipartite graphs: [Rosen, Sct. 10.2.4]; our criterium of bipartiteness is [Rozen, Sct. 10.4, Exerc. 63]. Chromatic number: [Rosen, Sct. 10.8]. Probabilistic method in combinatorics: [Rosen, Sct. 7.2.10].
- Ninth week: Ramsey theorem and Ramsey numbers: [11]. Trees are extensively covered in [Rosen, Sct. 11]. Various pieces of our "master" theorem (many equivalent definitions of a tree) are scattered along that chapter and exercises to it. Caeley's formula (without proof). Euler(ian) cycles/circuits: [Rosen, Sct. 10.5.2], the criterium: [Rosen, Sct. 10.5.2, Thm. 1]. Planar graphs: [Rosen, Sct. 10.7]. Fary's theorem: Wikipedia article. Kuratowski's Theorem: [Rosen, Sct. 10.7.3]. You can read about the colorful history of the four color theorem in [Rosen, page 763-764], and if you want more, see the Wikipedia article. The short story [12] on the subject is written by (perhaps) the best math popularizer of all time. Euler's formula [Rosen, Sct. 10.7.2]. Dual graphs: [Rosen, Sct. 10.8.1]. This fun YouTube video on a proof of Euler's formula via duality was contributed by a former student in this class. Vertices of degrees at most five: [Rosen, Sct. 10.7.2, Cor. 2]. Six-color theorem: [Rosen, Sct. 10.8, Exerc. 40]. Non-planarity of K_5 and K_{3,3}: [Rozen, Sct. 10.7.2, Examples 5,6].