CMSC 27130-1: Honors Discrete Mathematics

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

Office hours.

Theodoros Papamakarios
papamakarios@uchicago.edu
Crerar 207
Monday 10:30am-12pm Leonardo Coregliano
lenacore@uchicago.edu
Crerar 207
Tuesday 10am-11:30am Alexander Razborov
razborov@math.uchicago.edu
Ryerson 257E
Thursday 2pm-3:30pm

Lecture Notes 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 the beginning of class each Wednesday or at the end of Wednesday if submitted as a PDF prepared from a TeX source. The first set will be released on October 8 or October 9 (and due October 17). 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 a midterm and a final.
- Midterm: Friday November 2
- Final: Friday December 14, 10:30am-12:30pm

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.

J. Matousek, J. Nesetril, An Invitation to Discrete Mathematics, Oxford University Press, 2009.
L. Lovasz, Combinatorial Problems and Exercises, AMS Chelsea Publishing, 2007.
E. Mendelson, Introduction to Mathematical Logic, CRC Press, 2015.
S. Lang, Algebra, Springer, 8th edition, 2003.
G. Andrews, K. Erickkson, Integer Partitions, Cambridge University Press, 2004.
R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge University Press, 2007.
N. Alon, J. Spencer, The Probabilistic Method, Wiley-Interscience, 2008.
G. Sierksma, H. Hoogeveen, Seven criteria for integer sequences being graphic, Journal of Graph Theory 15, No. 2 (1991), 223-231.
M. Cvetkovic, M. Doob, H. Sachs, Spectra of Graphs: Theory and Applications, Huthig Pub Ltd, 1997.
L. Babai, Graph Isomorphism in Quasipolynomial Time.
P. Keevash, Hypergraph Turan Problems, Surveys in Combinatorics, Cambridge University Press, 2011, 83--140.
M. Gardner, The Island of Five Colors, in Fantasia Mathematica.

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. 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: Lexicographic ordering [Rosen, pages 620-622]. Ordinal arithmetic cntd. For more advanced things about ordinals see again any textbook in mathematical logic like [3, Sct. 4]. 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]. 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] or any textbook on abstract algebra, like (my favorite!) [4, Chapter 2].

Third week: Commutative rings cntd. Ideals: Wikipedia article or [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'' that also contains a sketch of the proof that $Z[\sqrt{-5}]$ is not a PID). Guest lectures: Professor Kurtz; see lectures 18 (second half) -- 21 of his course.

Fourth week: 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 2] is the example of $\mathbb Z_m$. Modular arithmetic itself is considered throughout [Rosen, Sct. 4]. Euler's function: [Rozen, page 272] and Wikipedia article. Fermat's Little Theorem [Rosen, Sct. 4.4, Theorem 3 and Exercise 19]. Chinese Remainder Theorem: [Rosen, pages 277-279]. 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]. 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: 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 (aka Twelvefold Way): [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]. Midterm.

Sixth week: Indist. balls, dist. boxes cntd. Indist. balls, indist. boxes: partitions [Rozen, page 431]. 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 theorem (without proof) and Mirsky theorem. Erdos-Szekeres theorem: [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 and mutually independent events: [Rosen, pages 457-458].
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]. Variance and its properties: [Rosen, pages 487-489]. Hoelder's inequality; for its consequence we mentioned in class, scroll down to the section "Probability measure". Jensen's inequality. Chebyshev's inequality: [Rosen, page 491]. Our light version of Chernoff's inequality and its proof is borrowed from the Wikipedia article (see also [6, Theorem 4.1]). Many more interesting (and much more sophisticated) "sharp concentration" bounds can be found in [7].

Eighth week (short): Graphs and degrees: [Rosen, Sct. 10.2] (Handshaking Theorem is [Rosen, Sct. 10.2, Thm.1]). More on degree sequences: [8], and this is Erdos-Gallai theorem in the nutshell. 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. Caeley's formula (we did Pitman's proof).

Ninth week: Moore graphs cntd. 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 [9]. Graph isomorphisms and graph invariants are discussed in [Rosen, Sct. 10.3]. Babai's quasi-polynomial algorithm for graph isomorphism: [10]. Basic terminology about subgraphs: [Rosen, pages 663-665]. Mantel and Turan's theorems. Extremal problems in hypergraphs: [11]. 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: [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.

Tenth week (short): Trees cntd. The Probabilistic Method, graphs without small cliques and independent sets: [Rozen, Sct. 7.2, Thm. 4]. Euler(ian) cycles/circuits: [Rosen, Sct. 10.5], and the main result is [Rosen, Thm. 1 on page 696]. Planar graphs: [Rosen, Sct. 10.7]. Kuratowski's Theorem: [Rosen, pages 724-725]. You can read about the colorful history of the four color theorem on [Rosen, page 728], and if that is not enough, see the Wikipedia article or\and read the short story [12] written by (perhaps) the best math popularizer of all time... 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 contributed by a former student. Dual graphs (implicitly): [Rozen, pages 722-723]. Non-planarity of K_5 and K_{3,3}: [Rozen, Examples 5,6 on page 723].