CMSC 27130/MATH 28130: Honors Discrete Mathematics

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

Office hours.

Alexander Razborov
razborov@math.uchicago.edu
Ryerson 257E
Monday 2pm-4pm Theodoros Papamakarios
papamakarios@uchicago.edu
Crerar 236
Tuesday 2pm-4pm Yiqiao Bao
ybao@uchicago.edu
Crerar 257
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 at the beginning of class each Wednesday or at the end of Wednesday if submitted as a PDF prepared from a TeX source. The first set will be released on October 5 (and due on October 13). You will be allowed to work together on solving homework problems, but all students must turn in their own write-ups of the 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 29 9:30am-10:20am
- Final: Thursday December 9 7:30am-9:30am
Literature. We will partly follow Discrete Mathematics and Its Applications (8th Edition) by K. Rosen; it should be available at the University bookstore. 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, 8th edition, 2003.
5. G. Andrews, K. Erickkson, Integer Partitions, Cambridge University Press, 2004.
6. N. Alon, J. Spencer, The Probabilistic Method, Wiley-Interscience, 2008.
7. M. Cvetkovic, M. Doob, H. Sachs, Spectra of Graphs: Theory and Applications, Wiley-VCH Verlag GmbH , 1999.
8. J. Verstraete, Extremal problems for cycles in graphs, in Recent Trends in Combinatorics, vol. 159, Springer, 2016.
9. P. Keevash, Hypergraph Turan Problems, Surveys in Combinatorics, Cambridge University Press, 2011, 83--140.
10. S, Jukna, Extremal Combinatorics, Springer-Verlag, 2011.
11. M. Ajtai, J. Komlos, E. Szemeredi, A note on Ramsey numbers, Journal of Combinatorial Theory, Series A, 29, No 3(1980), 354-360.
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: Introduction. Mathematical Induction: [Rosen, Section 5.1]. The sum of the first $n$ integers: [Rozen, Sct. 5.1.7, Example 1] and of the first $n$ cubes: [Rosen, Sct.5.1, Exercise 4]. Helly's theorem: Wikipedia article. A gentrified (but false all the same) version of the Horse Color Theorem: [Rozen Sct. 5.1.8]. 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]. Binary relations: [Rosen, Sct. 9.1]. Linear orderings: [Rosen, Sct. 9.6]. Partially ordered sets [Rosen, Sct. 9.6]. Quasi-orderings: [Rosen, page 669, Exercises 36-38]. 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].
- Second week: Well-ordered sets cntd. 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 where I learned this many years ago. 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] and the Euclidean Algorithm: [Rosen, Sct 4.3.7]. Lame's theorem (with slightly better bound than we did in class): [Rosen, Sct. 5.3.2, Theorem 1]. Univariate polynomials are ubiquitous in math, see the Wikipedia article. Gcd and Euclid's algorithm for univariate polynomials are extensively discussed in another Wikipedia article.
- Third week: 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 mine from [4] (Chapter 2 in this case). Ideals: Wikipedia article or [4, Chapter 2]. 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 PID). Equivalence relations: [Rosen, Sct. 9.5]; the partition theorem is [Rosen, Sct. 9.5.4, Thm. 2]. Factor-rings : [4, Chapter 2] in general and [Rosen, Sct. 9.5.2, Example 3] for our running example $\mathbb Z_n$. Modular arithmetic itself is considered throughout [Rosen, Sct. 4], in different contexts (see in particular [Rosen, Sct. 4.6] for connections to cryptography that I mentioned several times). Euler's theorem (without proof): Wikiipedia article. Fermat's Little Theorem [Rosen, Sct. 4.4.5]. Chinese Remainder Theorem (statement): [Rosen, Sct. 4.4.3].
- Fourth week: Chinese Remainder Theorem, existence (skipped): [Rosen, Sct. 4.4.3, Thm. 2]. Injective, surjective and bijective functions: [Rosen, Sct. 2.3]. Cantor-Schroeder-Bernstein Theorem (without proof): [Rosen, Sct. 2.5.3, Thm. 2]. Chinese Remainder Theorem, uniqueness: [Rosen, Sct. 4.4, Exercises 29 and 30]. 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: Inclusion-Exclusion cntd. Counting surjective functions [Rosen, Sct. 8.6.4]. Stirling numbers of the second kind [Rosen, pages 453-454]. For the recurrence relation see Wikiipedia 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 via binomial coefficients: [Rozen, page 452] (lucky day). Midterm.
- Sixth week: Indist. balls, indist. boxes: partitions [Rosen, page 454]. There are whole books (like [5]) entirely devoted to integer partitions. Pigeon-Hole-Principle: I recommend to read [Rosen, Sct. 6.2] for more beautiful examples of its application. Dilworth's theorem (without proof) and Mirsky's theorem. Erdos-Szekeres theorem: [Rosen, Sct. 6.2.3, Thm. 3]. 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].
- Seventh week: 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]. Markov's inequality: [Rosen, Exc. 37 on page 519]. Variance and its properties: [Rosen, Sct. 7.4.7]. Hoelder's inequality. Jensen's inequality. Chebyshev's inequality: [Rosen, Sct 7.4.8]. Chernoff's bound. Many more interesting (and much more sophisticated) "sharp concentration" bounds can be found in [6]. Graphs: [Rosen, Sct. 10.2].
- Eighth week: Graph degrees: [Rosen, Sct. 10.2]. Handshaking Theorem: [Rosen, Sct. 10.2, Thm.1]. Erdos-Gallai Theorem (just mentioned in class). Paths and connectivity: [Rosen, Sct. 10.4]. Path distance and diameter: [Rosen, Exerc. 52-53 on page 777]. Moore graphs. Adjacency matrices: [Rosen, Sct. 10.3.3]. Counting paths via adjacency matrices: [Rozen, Sct. 10.4.7, Theorem 2]. Spectral graph theory: [7]. 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 problem for even cycles: [8]. Extremal problems for hypergraphs: [9]. 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].
- Ninth week: Graphs without small cliques and independent sets, off-diagonal case: [11]. Diagonal case (aka Ramsey numbers): [Rosen, Sct. 7.2.10]. Trees are extensively covered in [Rosen, Sct. 11]. Various pieces of our "master" theorem (on many equivalent definitions of a tree) are scattered along that chapter and exercises to it. Caeley's formula (without proof). Planar graphs: [Rosen, Sct. 10.7]. Kuratowski's Theorem: [Rosen, Sct. 10.7.3]. Minors. Robertson-Seymour theorem (without proof). A catalogue of natural minor-closed families with known (and unknown) characterizations. 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. Hadwiger conjecture. 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. Our ``girth bound'' generalizes [Rosen, Sct. 10.7.2, Cor. 1,3]. Non-planarity of K_5 and K_{3,3}: [Rozen, Sct. 10.7.2, Examples 5,6]. Vertices of degrees at most five: [Rosen, Sct. 10.7.2, Cor. 2]. Six-color theorem: [Rosen, Sct. 10.8, Exerc. 40].