CMSC 27130/MATH 28130: Honors Discrete Mathematics

• Office hours.

  Alexander Razborov razborov@uchicago.edu Ryerson 360G Monday 3pm-5pm

  Nico Marin Gamboa jnicolasmg@uchicago.edu Regenstein 404 Tuesday 4pm-6pm

  Tiago Royer royertiago@gmail.com Crerar 207 Friday 4pm-6pm

• Lecture Notes of a previous version of the course are available, thanks to Yueheng Zhang for the effort! See also partial notes from previous years: 2016 and 2017. Use with care -- every year the content (slightly) evolves.

• Homeworks. There will be weekly homework assignments due on Wednesday on Gradescope via Canvas. The first set will be released on October 7 or 8 (and due on October 16). 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!
  • Assignment #1, due October 16
  • Assignment #2, due October 23
  • Assignment #3, due October 30
  • Assignment #4, due November 6
  • Assignment #5, due November 13
  • Assignment #6, due November 20
  • Assignment #7, due December 5

• Exams. There will be a midterm and a final.

  • Midterm: Friday November 1 9:30am-10:20am
  • Final: Wednesday December 11 10am-12pm (Ry 276)

• Literature. We will largely 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, 2nd edition, 2010.
  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. D. Cvetkovic, P. Rowlinson, S. Simic, An Introduction to the Theory of Graph Spectra, Cambridge University Press, 2009.
  10. J. Verstraete, Extremal problems for cycles in graphs, in Recent Trends in Combinatorics, vol. 159, Springer, 2016.
  11. P. Keevash, Hypergraph Turan Problems, Surveys in Combinatorics, Cambridge University Press, 2011, 83--140.
  12. S. Jukna, Extremal Combinatorics, Springer-Verlag, 2nd edition, 2011.
  13. R. Graham, B. Rothschield, J. Spencer, Ramsey Theory, Wiley-Interscience, 2nd edition, 1990.
  14. M. Gardner, The Island of Five Colors, in Fantasia Mathematica.

  Ongoing syllabus and references

  • First week: Induction and ordered sets. 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 (I called it Cat) 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]. 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].
  • Second week: 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. Number Theory. 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]. 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 (among many others, I learned my algebra from [4], see Chapter 2 for rings and ideals). Principal ideals and Bezout's theorem.
  • Third week: 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]. Euler's totient function and Euler's theorem (without proof), see e.g. Wikipedia article. Fermat's Little Theorem, also without proof: [Rosen, Sct. 4.4.5]. Chinese Remainder Theorem: [Rosen, Sct. 4.4.3]. A constructive proof of uniqueness in this theorem: [Rosen, page 302, Exerc. 29 and 30]. The RSA scheme is in [Rosen, Sections 4.6.3-4.6.7]; as always, if you need a few more details, the Wikipedia article is a good starting point. Counting subsets: the proof based on the product rule is [Rosen, Sct. 6.1.2, Example 10], and the inductive proof is [Rosen, Sct. 5.1.7, Example 10]. Basic counting principles: [Rosen, Sct. 6.1.2].
  • Fourth week: 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]. 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].
  • Fifth week: 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. Pigeon-Hole-Principle. Mirsky's theorem: Wikipedia article. Dilworth's theorem (without proof): Wikipedia article. Erdos-Szekeres theorem, ad hoc proof: [Rosen, Sct. 6.2.3, Thm. 3]. Dirichlet's Approximation Theorem: Wikipedia article. I recommend to read [Rosen, Sct. 6.2] for more beautiful examples of applications of the pigeon-hole principle. Probability spaces and events: [Rosen, Sct. 7.2]. Midterm.
  • Sixth week: 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, Section 7.3]; for the controversy mentioned in class see e.g. [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]. Conditional expectations and the law of total expectation: [Rosen, page 518].
  • Seventh week: 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]. Hoeffding inequality: [6, Theorem 2.2.2]; more generally, Chapter 2 is a very nice review of many other inequalities with a similar flavor. 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: [Rosen, Exerc. 52-53 on page 777]. 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 [8]).
  • Eighth week: 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 in [9]. 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: [10]. Extremal problems for hypergraphs: [11]; an excellent (albeit somewhat thin on graphs) text on extremal combinatorics in general: [12]. Bipartite graphs: [Rosen, Sct. 10.2.4]; our criterium of bipartiteness is [Rosen, Sct. 10.4, Exerc. 63]. Clique number, independence number and their simple properties: any textbook on graph theory. Lovasz theta function (just mentioned): Wikipedia article. Chromatic number: [Rosen, Sct. 10.8]. Probabilistic method in combinatorics: [Rosen, Sct. 7.2.10]. Ramsey theorem and Ramsey numbers: [Rosen, pages 425-426] or [13].
  • Ninth week: 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]. Hamiltonian cycles: [Rosen, Sct. 10.5.3] and Dirac's theorem (without proof): [Rosen, Sct. 10.5.3, Thm. 3]. Planar graphs: [Rosen, Sct. 10.7]. Fary's theorem (without proof). 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 [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. Vertices of degrees at most five: [Rosen, Sct. 10.7.2, Cor. 2]. Non-planarity of K_5 and K_{3,3}: [Rozen, Sct. 10.7.2, Examples 5,6]. Six-color theorem: [Rosen, Sct. 10.8, Exerc. 40]. Graph Minors. Hadwiger conjecture. Robertson-Seymour theorem (without proof).