CMSC 27100-1: Discrete Mathematics

Course description

Autumn10: Monday, Wednesday, Friday 11:30am-12:20pm (Ry 276)

Office hours.

Alexander Razborov
razborov@cs.uchicago.edu
Ryerson 154A
Monday 1:30pm-2:30pm and by appointment

Paolo Codenotti
paolo@cs.uchicago.edu
Ryerson 257A
Tuesday 4:30pm-6pm (note the change)

Pratik Worah
pworah@cs.uchicago.edu
Ryerson 257
Friday 2:30pm-4pm

Homeworks. There will be weekly homework assignments due at the beginning of class each Wednesday. The first set will be released on October 6 (and due October 13). You are encouraged to work together on solving homework problems. All students must turn in their own write-up of the solutions. If you work with other people, you must put their names clearly on the write-up.

Exams. There will be two midterms and a final.
- Midterm 1: Monday Oct. 25th
- Midterm 2: Friday Nov. 19th
- Final: Wednesday, Dec. 8th, 10:30am-12:30pm

Literature. We will follow Discrete Mathematics and Its Applications (6th Edition) by K. Rosen. It should be available at the Seminary co-op, and be on reserve in the math library. I also have one spare copy that I can loan to the class.
Here is some other literature sometimes cited below.
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. H. Cohn, R. Kleinberg, B. Szegedy, and C. Umans, Group-theoretic Algorithms for Matrix Multiplication.
4. S. Jukna, Extremal Combinatorics, Springer-Verlag, 2000.
5. G. Andrews, K. Erickkson, Integer Partitions, Cambridge University Press, 2004.
6. R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge University Press, 2007.
7. N. Alon, J. Spencer, The Probabilistic Method, Wiley-Interscience, 2008.

Progress and references.
- First week: Euclidean Algorithm is in [Rosen, Sct. 3.6]. An algorithm for the matching problem: [4, Section 5.4]. If you are adventurous (this classical text has trained generations of combinatorialists, but it is, well, difficult), you can also check out [2, Section 7] (see e.g. Problems 7.2-7.4). If you liked our proof of the Pythagorean Theorem, you may want to explore this link (our proof is #9). Maximizing happiness in the football player problem is scientifically known as Max Cut problem, and our approach to it is a typical greedy algorithm (you can read more about it in [Rosen, pages 174-176]). The complexity analysis of the Euclidean Algorithm is in [Rosen, Sct. 4.3], and our discussion about running time, worst-case, average-case etc. is echoed in [Rosen, Sct. 3.3]. The definition of big-O is [Rosen, Definition 1 on page 180].
- Second week: all the simple facts about asymptotic growth (and a few more) can be found in [Rosen, Section 3.2]. The discussion about right signs to be used as well as history of the notation can be found both there and in the Wikipedia article. Both sources also contain their versions of the Function Growth Zoo (in Rosen's book it's on page 196), but they are less detailed than what we did in class. Searching Algorithms: [Rosen, pages 170-172] and their complexity analysis is in [Rosen, Examples 2 and 3 on page 194]. I do not know of any good source that would cover our lower bounds for searching and sorting (let me know if you know one), they are very simple anyway. Sorting Algorithms: [Rosen, pages 172-174], except for more complicated Merge Sort that is in [Rosen, Section 4.4]. Inversion complexity: [1, Exc. 6 after Chapter 3.2]. Matrix multiplication: [Rosen, Section 3.8], as I said, $n^{\sqrt 7}$ after Example 5 should probably read $n^{\log_2 7}$. The most recent and promising ideas I mentioned can be found in [3] (bear with the fact that it is a serious research paper, of course). Our spontaneous discussion on public-key cryptography is somewhat reflected in [Rosen, pages 241-244].
- Third week: An entire course on graph theory will be taught by the guest lecturer this spring, CMSC 275. Graph theory is covered in Chapters 9 and 10 of Rosen. Planarity and coloring are sections 9.7 and 9.8. An extensive discussion of the four color theorem can be found here, which is written by one of the authors of the latest proof. A fuller discussion of the ideas around the proof and related topics can be found in an American Mathematical Society feature column "Colorful mathematics". The mathworld site on Kuratowski's theorem contains links to the proof and the history of the result. Induction! We will see it again soon, but if you want to prepare for this encounter in advance, consult [Rosen, Section 4] (or at least [Rosen, Section 4.1]).
- Fourth week: all this material is simple and classical and well covered in our textbook. Counting subsets: the first proof is in [Rosen, Sct. 4.1, Example 9] and the second proof is [Rosen, Sct. 5.1, Example 10]. Buzzwords about functions: [Rosen, Sct. 2.3]. Counting functions and injective functions (permutations): [Rosen, Sct. 5.1 and Sct. 5.3]. Binomial coefficients and identities: [Rosen, Sct. 5.4]. Inclusion-Exclusion principle: [Rosen, Sct. 5.1 and 7.5].
- Fifth week (short): Counting surjective functions is somewhat covered in [Rosen, pages 509-510], but we gave a direct proof. Pascal's identity and triangle, and Vandermonde's identity are in [Rosen, Sct. 5.4] (but we did them in the reverse order). Multinomial coefficients are in [Rosen, Exc. 62, 63 after Sct. 5.5]. The game of Objects and Boxes (we called it Balls and Pockets) is played in [Rosen, pages 376-379] but we significantly emphasized the mathematical meaning of all this. In particular, you can read more on equivalence relations in [Rosen, Section 8.5]. Wikipedia article on Gamma functions is good (as you can see from it, I was dead wrong: negative integers are the only complex numbers where the factorial is not defined). One very useful application of "non-integer factorials" in combinatorics is Lovasz's version of Kruskal-Katona theorem [2, Exc. 13.31(b)]. And there are thick books (like [5]) entirely devoted to one subject: partitions.
- Sixth week: Trees are extensively covered in [Rosen, Sct. 10.1]. Various pieces of our "tree description" theorem are scattered along that chapter and exercises to it. Spanning trees: [Rosen, Sct. 10.4]. Our proof of Cayley's formula is a slightly modified version of Pitnam's proof, the latter sometimes referred to as “the most beautiful of them all.” It can be found (along with some useful references) in the Wikipedia article on double counting. Probability spaces, events, conditional probability and independence: [Rosen, Sct. 6.2].
- Seventh week: Bayes' Theorem is covered in [Rosen, Sct. 6.3] (and in many more details than we did in the class). Theorem of total probability is not explicit in the book, but it appears in the proof of [Rosen, Sct. 6.3, Thm. 1]. Mutually independent events -- [Rosen, Exerc. 23 on page 444]. Random variables -- [Rosen, Sct. 6.2], expectations and their linearity -- [Rosen, Sct. 6.4]. Binomial distribution -- [Rosen, Sct. 6.2]. Poisson distribution is not in Rosen's book; the Wikipedia article with the same name is a good source of further information. Geometric distribution: [Rosen, pages 433-434]. Independent random variables: [Rosen, pages 434-436]. Indicator random variable: [Rosen, Exerc. 20 on page 440] (we called it $\chi_A$ in the class).
- Eighth week (short): Markov's Inequality: [Rosen, Exerc. 31 on page 441]. Variance and Chebyshev's inequality: [Rosen, Sct. 6.4]. Hashing is marginally touched upon in [Rosen, pages 205-206 and pages 410-411], but randomized (and, in particular, universal) hashing is not discussed in the textbook. Check out Wikipedia article or, for more comprehensive treatment, [6, Sct. 8.4].
- Ninth week (short): Our light version of Chernoff's inequality and its proof is borrowed from a Wikipedia article (see also [6, Theorem 4.1]). Many more interesting (and much more sophisticated) "sharp concentration" bounds can be found in [7]. Although the "canonical" example of an application of the probabilistic method in combinatorics can be found in [Rosen, Thm. 4 on page 413], a standard reference on this subject is also [7] (as witnessed by its title). In particular, the examples we did in the class are [7, Theorem 2.2.1], [7. Theorem 2.1.1] and [7, Theorem 1.2.1] (the latter is also [Rosen, Exerc. 39 on page 416]).
- Tenth week (short): As I warned in the class, we are not aware of any book where Markov chains would be covered in a suitable style and at a suitable level. As (well, almost) always, Wikipedia article is a good starting point, and Chapter 8 in Prof. Babai's notes is very close to what we did, albeit slightly more advanced.