CMSC 27130-1: Honors Discrete Mathematics

Course description

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

Office hours.

Zihan Tan zihantan@uchicago.edu Eckhart 131 Monday 3pm-4:30pm	Leonardo Coregliano lenacore@uchicago.edu Theory Lounge Ryerson 162 Tuesday 10am-11:30am
Alexander Razborov razborov@math.uchicago.edu Ryerson 257E Wednesday 10:30am-12pm	Christopher Jones csj@uchicago.edu Theory Lounge Ryerson 162 Friday 12pm-1:30pm

Lecture notes are downloadable as a single PDF file. Any comments, corrections and suggestions are most welcome.

Homeworks. There will be weekly homework assignments due at the beginning of class each Wednesday. The first set will be released on October 3 or October 4 (and due October 12). You are 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 two midterms and a final.
- Midterm 1: Monday October 17
- Midterm 2: Friday November 11
- Final: Friday December 9

Literature. We will partly follow Discrete Mathematics and Its Applications (7th Edition) by K. Rosen; it should be available at the Seminary co-op. 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 a 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. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, 3rd edition, 2009.
5. S. Lang, Algebra, Springer, 8th edition, 2003.
6. G. Andrews, K. Erickkson, Integer Partitions, Cambridge University Press, 2004.
7. R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge University Press, 2007.
8. N. Alon, J. Spencer, The Probabilistic Method, Wiley-Interscience, 2008.
9. G. Sierksma, H. Hoogeveen, Seven criteria for integer sequences being graphic, Journal of Graph Theory 15, No. 2 (1991), 223-231.
10. M. Cvetkovic, M. Doob, H. Sachs, Spectra of Graphs: Theory and Applications, Huthig Pub Ltd, 1997.
11. L. Babai, Graph Isomorphism in Quasipolynomial Time.
12. P. Keevash, Hypergraph Turan Problems, Surveys in Combinatorics, Cambridge University Press, 2011, 83--140.

Ongoing syllabus and references.
- First week: Introduction. Mathematical Induction: [Rosen, Section 5.1]. The sum of the first $n$ integers: [Rozen, Sct. 5.1, Example 1] and of the first $n$ cubes: [Rosen, Sct.5.1, Exercise 4]. Helly's theorem: Wikipedia article. The case $d=1$ is (essentially) [Rosen, Sct. 5.1, Exerc. 73]. Strong Induction: [Rosen, Sct. 5.2]. Fundamental theorem of arithmetic [Rosen, Sct. 4.3, Theorem 1]. Induction vs. recursion: [Rosen, Sct. 5.3]. Well-ordering property: [Rosen, pages 340-341]. Partial and linear orderings: [Rosen, Sct. 9.6]. You can read about linear extensions in the Wikipedia article. After all, it does not seem to be equivalent to the full Axiom of Choice, and in the section "Related results" you can read about algorithmic aspects of that problem. It is also known as "topological sorting" (and a host of other names), see [Rosen, Algorithm 1 on page 628] for a more structured approach to it. Well-ordered sets: [Rosen, Sct. 9.6, Defintion 4]; transfinite induction: [Rosen, Sct. 9.6, Thm. 1]. Ordinal arithmetic: Wikipedia article or any textbook in mathematical logic like [3, Sct. 4.2] if you want it at a deeper level.
- Second week: Ordinal arithmetic cntd. For more advanced things we briefly mentioned in class (ordinals are always conmparable, every set can be well-ordered given AC) see again any textbook in mathematical logic like [3, Sct. 4] or sign up for our course on the subject. Proof of uniqueness in the Fundamental Theorem of Arithmetic modulo the main lemma: [Rozen, page 271]. Greatest common divisor: [Rosen, Sct. 4.3, Def. 2]. Guest lectures (Wednesday, Friday) by Professor Simon: solving recurrent sequences [4, Sct. 4.3-4.6].
- Thrid week: Bezout's Theorem and the Euclidean Algorithm: [Rosen, Sct 4.3]. Its complexity analysis (slightly tighter than ours): [Rosen, Sct. 5.3, Thm. 1]. Axioms of a commutative ring: [Rosen, page 243]. You can read about commutative rings and ideals in Wikipedia article or in any textbook on abstract algebra, like (my favorite!) [5, Chapter 2]. Noetherian rings: [5, Chapter 6]; Hilbert's basis theorem: [5, Sct. 6.2]. Principle 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''), Equivalence relations: [Rosen, Sct. 9.5]; the partition theorem is [Rosen, Sct. 9.5, Thm. 1]. Factor-rings is again [5, Chapter 2] in general and [Rosen, Sct. 9.5, Example 2] is the example of $\mathbb Z_m$. Modular arithmetic itself is considered throughout [Rosen, Sct. 4], and the Chinese Remainder Theorem is [Rosen, pages 277-279] (according to Rosen, it is 2k years old and it does seem to have a specific name attached to it).
- Fourth week: Midterm. Chinese Remainder Theorem cntd. Counting subsets: the first proof is in [Rosen, Sct. 5.1, Example 10] (notice the nice picture!) and the second proof is [Rosen, Sct. 6.1, Example 10]. Injective, surjective and bijective functions: [Rosen, Sct. 2.3]. Cantor-Schroeder-Bernstein Theorem: Wikipedia article. Counting functions and injective functions (permutations): [Rosen, Sct. 6.1, Examples 6 and 7], [Rosen, Sct. 6.3, Example 1]; the same section contains many other simple applications of our basic rules. Binomial coefficients: [Rosen, Sct. 6.4].
- Fifth week: Binomial coefficients cntd. Vandermonde's identity, Pascal's identity and Pascal's triangle: [Rosen, Sct. 6.4] (note that unlike us he goes from Pascal's identity to Vandermonde' Theorem). Binomial Theorem: [Rosen, Sct. 6.4]. Inclusion-Exclusion Principle: [Rosen, Sct. 8.5] and counting surjective functions is [Rosen, Sct. 8.6, Thm. 1]. The Ball Game: [Rosen, pages 428-431]. Distinguishable balls, distinguishable boxes: multinomial coefficients [Rozen, page 429, Theorem 4]. Dist. balls, indist. boxes: Stirling numbers of the second kind [Rozen, pages 430-431]. Indist. balls, dist. boxes: a lucky day [Rozen, pages 424-425]. Indist. balls, indist. boxes: partitions [Rozen, page 431]. There are whole books (like [6]) entirely devoted to integer partitions, and an excellent recap of (practically) all the materials, and a bit more, we did in the counting block is called Twelvefold way. Pigeon-Hole-Principle: I recommend to read [Rosen, Sct. 6.2] for more beautiful examples of its application. Dilworth theorem (without proof) and Mirsky theorem.
- Sixth week: Erdos-Szekeres theorem (a direct proof): [Rosen, Sct. 5.2, Thm. 3]. Dirichlet's approximation theorem. Roth's theorem (without proof). Probability spaces and events: [Rosen, Sct. 7.2]. Conditional probability: [Rosen, Sct. 7.2]. Independent events: [Rosen, pages 457-458]. Bayes' Theorem is covered in [Rosen, Sct. 7.3] (in many more details than we did in the class). You can read about the controversy surrounding it in this thought-provoking article. The formula of total probability is not explicit in Rosen's book, but it appears in the proof of [Rosen, Sct. 7.3, Thm. 1]. Random variables: [Rosen, pages 460-461], and this is how pushforward measures (of which pushforward probability distributions is a special case) look in the "real" world. Binomial distribution: [Rosen, pages 458-460]. Poisson distribution.
- Seventh week: Geometric distribution: [Rosen, pages 484-485]. 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, pages 485-487]. Markov's inequality: [Rosen, Exc. 37 on page 493]. Variance and its properties: [Rosen, pages 487-489]. What I called in class "Hoelder inequality" is actually its rather special case (thanks for pointing this out), here is the full version: Wikipedia article. Jensen inequality. Chebyshev's inequality: [Rosen, page 491]. Midterm.
- Eighth week: Our light version of Chernoff's inequality and its proof is borrowed from a Wikipedia article (see also [7, Theorem 4.1]). Many more interesting (and much more sophisticated) "sharp concentration" bounds can be found in [8]. Graphs and degrees: [Rosen, Sct. 10.2] (Handshaking Theorem is [Rosen, Sct. 10.2, Thm.1]). More on degree sequences: [9]. Most of the material on paths and connectivity is from [Rosen, Sct. 10.4]; for the path distance and diameter see [Rosen, Exerc. 52-53 on page 680]. Moore graphs. Adjacency matrices: [Rosen, Sct. 10.3]. Counting paths via adjacency matrices: [Rozen, Sct. 10.4, Theorem 2]. A good reference on the spectral graph theory is [10]. Graph isomorphisms and graph invariants are discussed in [Rosen, Sct. 10.3]. Babai's quasi-polynomial algorithm for graph isomorphism: [11]. Basic terminology about subgraphs: [Rosen, pages 663-665]. Mantel and Turan's theorems. Extremal problems in hypergraphs: [12].
- Nineth week (short): Bipartite graphs: [Rosen, pages 656-658]; our criterium of bipartiteness is [Rozen, Sct. 10.4, Exerc. 63]. Clique number: [Rosen, pages 739-742]. Chromatic number: [Rosen, Sct. 10.8]. Graphs without small cliques and independent sets (statement): [Rozen, Sct. 7.2, Thm. 4]. Trees are extensively covered in [Rosen, Sct. 11.1]. Various pieces of our "master" theorem (on many equivalent definitions of a tree) are scattered along that chapter and exercises to it. Euler(ian) cycles/circuits: [Rosen, Sct. 10.5], and the main result is [Rosen, Thm. 1 on page 696].
- Tenth week (short): Graphs without small cliques and independent sets (proof). Hamiltonian cycles: [Rosen, Sct.10.5]. Dirac's theorem (actually, even a stronger statement) is proved in [Rosen, Exerc. 65 on page 707]. Planar graphs: [Rosen, Sct. 10.7]. Kuratowski's Theorem: [Rosen, pages 724-725] Graph minors are not covered there, see Wikipedia article on minors. You can read about the colorful history of the four color theorem on [Rosen, page 728]. Our proof of Euler's formula is inspired by [Rosen, Exerc. 18 on page 726]. Notice an important twist here: we do not assume the original formula for connected graphs, but, on the contrary, deliberately prove at once a stronger statement to make our life (by induction) simpler. If you prefer visual proofs, check out this YouTube video.