CMSC 27130-1: Honors Discrete Mathematics

Course description

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

• Office hours.

  Alexander Razborov razborov@math.uchicago.edu Ryerson 257E Monday 1:30pm-3pm

  Nathan Mull nmull@uchicago.edu Theory Lounge Ryerson 162 Tuesday 2pm-3:30pm

  Christopher Jones csj@uchicago.edu Eckhart 131 Friday 10:30am-12pm

• Some Lecture notes from the previous year and from this one are available.

• Homeworks. There will be weekly homework assignments due at the beginning of class each Wednesday. The first set will be released on October 2 or October 3 (and due October 11). 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!
  • Assignment #1, due October 11
  • Assignment #2, due October 18
  • Assignment #3, due October 25
  • Assignment #4, due November 1
  • Assignment #5, due November 8
  • Assignment #6, due November 15
  • Assignment #7, due November 22
  • Assignment #8, due November 29

• Exams. There will be two midterms and a final.

  • Midterm 1: Monday October 16
  • Midterm 2: Friday November 10
  • Final: Wednesday December 6 10:30am

• 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.

  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. S. Jukna, Extremal Combinatorics, Springer-Verlag, 2nd edition, 2011.
  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.
  13. M. Gardner, The Island of Five Colors, in Fantasia Mathematica.

• Ongoing syllabus and references.
  • First week: Introduction. Warm-up: Bezout's Theorem and the Euclidean Algorithm [Rosen, Section 4.3], You may also want to check out [Rosen, Exercise 36 to Sct. 5.2] to see how the same argument looks in consistently mathematical notation. 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].

  • Second week: You can read about linear extensions in the Wikipedia article. 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 to learn more. Proof of uniqueness in the Fundamental Theorem of Arithmetic modulo the main lemma: [Rozen, page 271]. Proof of the main lemma from Bezout's theorem [ibid]. The complexity analysis of the Euclidean algorithm (slightly tighter than ours): [Rosen, Sct. 5.3, Thm. 1]. Polynomial division: Wikipedia article

  • Third week: You can read about commutative rings and ideals in Wikipedia article or in any textbook on abstract algebra, like (my favorite!) [4, Chapter 2]. Noetherian rings: [4, Chapter 6]; Hilbert's basis theorem: [4, 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 [4, Chapter 2] in general and [Rosen, Sct. 9.5, Example 3] is the example of $\mathbb Z_m$. Can you see what is the factor-object corresponding to [Rosen, Sct. 9.5, Example 2]? Inductive loading [Rosen, Sct. 5.1, Exercise 74]. Modular arithmetic is considered throughout [Rosen, Sct. 4], and the Chinese Remainder Theorem is [Rosen, pages 277-279].

  • Fourth week: Midterm. Chinses 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.Dense linear orderings without endpoints: 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 [5]) 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.
  • Sixth week: Pigeon-Hole-Principle: I recommend to read [Rosen, Sct. 6.2] and/or [6, Sct. 4] for more beautiful examples of its application. Erdos-Szekeres theorem: [Rosen, Sct. 6.2, Thm. 3] or [6, Sct. 4.2]. Dirichlet's approximation theorem: [6, Sct. 4.5]. 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.
  • Seventh week: 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. 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]. Midterm.
  • Eighth week:Variance and its properties: [Rosen, pages 487-489]. Hoelder's inequalty and Jensen's inequality. Chebyshev's inequality: [Rosen, page 491]. Chernoff's bound (without proof): Wikipedia article or [7, Theorem 4.1]. Many more interesting 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]. [6] is a highly recommended reading on extremal combinatorics. Mantel and Turan's theorems.
  • Nineth week (short): Mantel's theorem cntd. Extremal problems in hypergraphs: [12]. Bipartite graphs: [Rosen, pages 656-658]; our criterium of bipartiteness is [Rozen, Sct. 10.4, Exerc. 63]. Clique number: [Rosen, pages 739-742]. Caeley's formula (we did Pitman's proof).
  • Tenth week (short): Chromatic number: [Rosen, Sct. 10.8]. Graphs without small cliques and independent sets (without proof): [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. 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] or in the Wikipedia article on Four-Color Theorem. [13] is the science fiction story I was referring to. 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. Dual graphs (implicitly) with applications: [Rozen, pages 722-723].