CMSC 27130/MATH 28130: Honors Discrete Mathematics

Autumn 22: Monday, Wednesday, Friday 9:30am-10:20am (Stuart 102)

Office hours.

Alexander Razborov
razborov@uchicago.edu
Ryerson 360G
Monday 2pm-4pm Cameron Chang
changca@uchicago.edu
Crerar 236
Tuesday 2pm-4pm Theodoros Papamakarios
papamakarios@uchicago.edu
Crerar 236
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. The first set will be released on October 4 (and due on October 12). 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 28 9:30am-10:20am
- Final: December 6, 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. B. Efron, A 250-Year Argument: Belief, Behavior, and the Bootstrap.
7. R. Vershinin, High-Dimensional Probability, Cambridge University Press, 2018.
8. P. Biggs, Strongly Regular Graphs with no Triangles, 2009.
9. J. Verstraete, Extremal problems for cycles in graphs, in Recent Trends in Combinatorics, vol. 159, Springer, 2016.
10. P. Keevash, Hypergraph Turan Problems, Surveys in Combinatorics, Cambridge University Press, 2011, 83--140.
11. S. Jukna, Extremal Combinatorics, Springer, 2011.
12. R. Graham, B. Rothschield, J. Spencer, Ramsey Theory, 2nd edition,1990.
13. M. Ajtai, J. Komlos, E. Szemeredi, A note on Ramsey numbers, Journal of Combinatorial Theory, Series A, 29, No 3(1980), 354-360.
14. 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]. Linear (or total) quasi-orderings: quasi-orderings + totality. Linear extensions of a poset: [Rosen, Sct. 9.6.6] ; our proof is slightly different. 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 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].
- Third week: 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. 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). 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]. 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 (mentioned very briefly) : [4, Chapter 2]. For applications of modual arithmetic to cryptography see [Rosen, Sct. 4.6]. 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 cntd. 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]. Counting surjective functions [Rosen, Sct. 8.6.4]. Stirling numbers of the second kind [Rosen, pages 453-454].
- Fifth week: 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. For the recurrence relation see Wikipedia article. Indist. balls, dist. boxes: binomial coefficients again: [Rozen, page 452] (lucky day). Indist. balls, indist. boxes: partitions [Rosen, page 454]. There are whole books [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]. Dirichlet's Approximation Theorem. Midterm.
- Sixth week: Roth's theorem (without proof). 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]. Bayesian law: [Rosen, Sct. 7.3]. For the controversy mentioned in class see [6]. 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].
- Seventh week: 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: [7, Theorem 2.3.1]; more generally, Chapter 2 is a very nice review of many other inequalities with a similar flavor mentioned in class. Graphs: [Rosen, Sct. 10.2]. Graph degrees: [Rosen, Sct. 10.2]. Handshaking Theorem: [Rosen, Sct. 10.2, Thm.1]. Erdos-Gallai Theorem (without proof). Paths and connectivity: [Rosen, Sct. 10.4]. Path distance and diameter: [Rosen, Exerc. 52-53 on page 777]. Moore bound and Moore graphs.
- Eighth week: Moore graphs cntd. Strongly regular graphs (for the triangle-free case see [8]). Adjacency matrices: [Rosen, Sct. 10.3.3]. Counting paths via adjacency matrices: [Rozen, Sct. 10.4.7, Theorem 2]. 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: [9]. Extremal problems for hypergraphs: [10]. An excellent (albeit somewhat thin on graphs) text on extremal combinatorics in general: [11]. Bipartite graphs: [Rosen, Sct. 10.2.4]; our criterium of bipartiteness is [Rozen, Sct. 10.4, Exerc. 63]. Chromatic number: [Rosen, Sct. 10.8]. Ramsey theorem and Ramsey numbers [12]. Off-diagonal case: [13]. Diagonal case, probabilistic method in combinatorics: [Rosen, Sct. 7.2.10].
- Ninth week: 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). Euler(ian) cycles/circuits: [Rosen, Sct. 10.5.2], the criterium: [Rosen, Sct. 10.5.2, Thm. 1]. Hamilton(ian) cycels: [Rosen, Sct. 10.5.3]. Dirac's theorem: [Rosen, Sct. 10.5.3, Thm. 3]. Planar graphs: [Rosen, Sct. 10.7]. Kuratowski's Theorem: [Rosen, Sct. 10.7.3]. Minors (very briefly). 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 [14] 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. 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]. Robertson-Seymour theorem (without proof). A catalogue of natural minor-closed families with known (and unknown) characterizations.