CMSC 27130/MATH 28130: Honors Discrete Mathematics

• Office hours.

  Alexander Razborov razborov@math.uchicago.edu Zoom and Ryerson 257E (at most 3 students at a time) Monday 10:30am-12pm

  Leonardo Coregliano lenacore@uchicago.edu Zoom Tuesday 10am-11:30am

  Theodoros Papamakarios papamakarios@uchicago.edu Zoom Thursday 2pm-3:30pm

• 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 11:59pm each Wednesday on Canvas. Work submitted as a PDF prepared from a TeX source will earn 3 points of extra credit. If you work is hand-written please double check that your scanned file is legible before submitting. The first set will be released on October 6 (and due on October 14). 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!
  • Assignment #1, due October 14
  • Assignment #2, due October 21
  • Assignment #3, due October 28
  • Assignment #4, due November 4
  • Assignment #5, due November 11
  • Assignment #6, due November 18
  • Assignment #7, due December 2

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

  • Midterm: Friday October 30 9:10am-10am
  • Final: Friday December 11 10:30am-12:30pm

• Literature. We will partly follow Discrete Mathematics and Its Applications (8th 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 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. 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, 2016.
  12. J. Verstraete, Extremal problems for cycles in graphs, in Recent Trends in Combinatorics, vol. 159, Springer, 2016.
  13. P. Keevash, Hypergraph Turan Problems, Surveys in Combinatorics, Cambridge University Press, 2011, 83--140.
  14. M. Ajtai, J. Komlos, E. Szemeredi, A note on Ramsey numbers, Journal of Combinatorial Theory, Series A, 29, No 3(1980), 354-360.
  15. 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]. 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. Strong Induction and Well-Ordering: [Rosen, Sct. 5.2]. Fundamental theorem of arithmetic [Rosen, Sct. 4.3.2, Theorem 1]. Induction vs. recursion: [Rosen, Sct. 5.3]. Well-ordering property: [Rosen, Sct. 5.2.5]. Binary relations: [Rosen, Sct. 9.1]. Linear orderings: [Rosen, Sct. 9.6].
  • Second week: Partially ordered sets [Rosen, Sct. 9.6]. Linear extensions of a poset: [Rosen, Sct. 9.6.6] (the topological ordering is more structured approach than the simple apple/orange idea I sketched in class). You can read more about linear extensions in the Wikipedia article. Well-ordered sets: [Rosen, Sct. 9.6, Defintion 4]; transfinite induction: [Rosen, Sct. 9.6, Thm. 1]. 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]. Univariate polynomials are ubiquitous in math, the Wikipedia article provides a good overview as well as a review of the main operations on polynomials, accompanied with examples.
  • 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). Lame's theorem (slightly better than what we did in class): [Rosen, Sct. 5.3.2, Theorem 1]. 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). Lagrange's theorem: Wikiipedia article or [4, Chapter 1.2, Proposition 1]. Euler's theorem: Wikiipedia article. Fermat's Little Theorem [Rosen, Sct. 4.4.5]. Chinese Remainder Theorem: [Rosen, Sct. 4.4.3]. Injective, surjective and bijective functions (sneak preview): [Rosen, Sct. 2.3].
  • Fourth week: Counting subsets: the first proof is in [Rosen, Sct. 5.1.7, Example 10] (notice the nice picture!), and the second proof is [Rosen, Sct. 6.1.2, Example 10]. Injective etc. functions, official introduction: [Rosen, Sct. 2.3]. Cantor-Schroeder-Bernstein Theorem, without proof but with an engaging discussion: [Rosen, Sct. 2.5.3, Thm. 2]. Basic counting principles: [Rosen, Sct. 6.1.2]. Counting functions and injective functions (sometime 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] and counting surjective functions is [Rosen, Sct. 8.6.4].
  • Fifth week: Counting surjective functions cntd. Stirling numbers of the second kind [Rosen, pages 453-454]. 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). 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. Midterm.
  • Sixth week: Erdos-Szekeres theorem: [Rosen, Sct. 6.2.3, 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.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.
  • Seventh week: 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]. Jensen's inequality. Hoelder's inequality; for its special case we mentioned in class, scroll down to the section "Probability measure". Chebyshev's inequality: [Rosen, Sct 7.4.8]. Chernoff's inequality (without proof) 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: [Rosen, Sct. 10.2, Thm.1]. Erdos-Gallai Theorem (without proof). More on degree sequences: [9]. Paths and connectivity: [Rosen, Sct. 10.4]. Path distance and diameter: [Rosen, Exerc. 52-53 on page 777]. Moore's bound.
  • Eighth week: Moore's bound and graphs cntd. Adjacency matrices: [Rosen, Sct. 10.3.3]. Counting paths via adjacency matrices: [Rozen, Sct. 10.4.7, 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, Sct. 10.2.7]. Mantel and Turan's theorems. Extremal problem for even cycles: [12]. Extremal problems for hypergraphs: [13]. Bipartite graphs: [Rosen, Sct. 10.2.4]; our criterium of bipartiteness is [Rozen, Sct. 10.4, Exerc. 63]. Chromatic number: [Rosen, Sct. 10.8]. Graphs without small cliques and independent sets, off-diagonal case: [14]. Diagonal case: [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. Wagner's theorem (without proof). 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 [15] on the subject is written by (perhaps) the best math popularizer of all time. Hadwiger conjecture. Euler's formula [Rosen, Sct. 10.7.2]. This fun YouTube video was contributed by a former student in this class. Dual graphs: [Rosen, Sct. 10.8.1]. 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].