CMSC 27100-1: Discrete Mathematics

Course description

Autumn09: 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
Friday 1:30pm-3pm

Ankan Saha
ankans@cs.uchicago.edu
Ryerson 257
Tuesday 5pm-6:30pm

Homeworks. There will be weekly homework assignments due at the beginning of class each Wednesday. The first set will be released on October 7 (and due October 14). 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. Tentative (!) dates are:
- Midterm 1: Monday Oct. 26th
- Midterm 2: Friday Nov. 20th
- Final: Monday, Dec. 7th, 10:30-12:30

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.
Another nice reference text: An Invitation to Discrete Mathematics by Matousek and Nesetril

Progress and references.
- First (short) week: Euclidean Algorithm is in [Rosen, Sct. 3.6]. If you liked our proof of the Pythagorean Theorem, you may want to explore this link (our proof is #9). The original football players problem is closely related to the MAXIMUM CUT (aka MAX-CUT) problem, and the *^1000 challenge is about the behavior of simple Hopfield neural networks. In both cases, Wikipedia articles might be a good source of the most basic information. Our proof of undecidability of the Halting Problem followed [Rosen, Sct. 3.1] very closely. The complexity analysis of the Euclidean Algorithm is in [Rosen, Sct. 4.3], and the discussion about the difference between polynomial and exponential can be found in [Rosen, Sct. 3.3]. Our proof of undecidability of the Halting Problem followed [Rosen, Sct. 3.1] very closely.
- Second week: 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].
- Third week: Counting surjective functions is somewhat covered in [Rosen pp. 509-510], but we gave a direct proof. More on binomial coefficients: Pascal's identity and triangle, and Vandermonde's identity are in [Rosen, 5.4]. More counting: Multinomial coefficients, "balls and sticks", partitions of a set into blocks, and how these all count ways to put objects in boxes is covered in [Rosen 5.5], the multinomial theorem is in [Rosen 5.5, exercises 62, 63]. Partition numbers are also in [Rosen 5.5], but we did a little more about young tableaux. For the pigeon hole principle, we followed [Rosen 5.2] fairly closely, although our proof of theorem 3 was a little different.
- Fourth week: Probability spaces, events, conditional probability and independence: [Rosen, Sct. 6.2]. 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 explicitly 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.
- Fifth (short) week: All material (expectation, variance, their properties and Chebyshev's inequality) is classical and is borrowed from [Rosen, Sct. 6.4] with little to no changes. Markov's Inequality is [Rosen, Exerc. 31 on page 441]. Poisson distribution is not in Rosen's book; the Wikipedia article is a good source of further information. And this is a zoo of other important distributions.
- Sixth week: Our light version of Chernoff's inequality and its proof is borrowed from the Wikipedia article http://en.wikipedia.org/wiki/Chernoff_bound (see also Theorem 4.1 in the book "Randomized Algorithms" by Motwani, Raghavan). Many more interesting (and much more sophisticated) "sharp concentration" bounds can be found in "The probabilistic method" by Alon and Spencer that is sort of a standard reference on this topic. Graphs and degrees: [Rosen, Sct. 9.2]. The original paper by Erdos and Gallai (characterization of degree sequences) is in Hungarian. If you can not read it, you can check out G. Sierksma and H. Hoogeveen, "Seven criteria for integer sequences being graphic, " Journal of Graph Theory 15, No. 2 (1991) 223–231. More material on degree sequences can be found in [Rosen, Exerc. 30-40 on page 610]. Most of the material on paths and connectivity is from [Rosen, Sct. 9.4]; for the path distance and diameter see [Rosen, Exerc. 38 on page 680]. As in many other cases, the Wikipedia article http://en.wikipedia.org/wiki/Moore_graph is a good referral point for Moore graphs. Graph isomorphisms and graph invariants are discussed in [Rosen, Sct. 9.3].
- Seventh week: Wikipedia article is a good entertaining reading about interactive proofs, including a reference to the original paper containing the protocol for graph non-isomorphism. Subgraphs: [Rosen, Sct. 9.2]. Wikipedia article contains a generalization of Mantel's theorem to Kr-free graphs (aka Turan's theorem), but, as you can see, the proof is already significantly more complicated. Bipartite graphs: [Rosen, Sct. 9.2]; for more information (including our criterium) see Wikipedia article. Chromatic number: [Rosen, Sct. 9.8]; clique and independence number: [Rosen, pages 678-681]. This article about Shannon capacity refers to the seminal paper by Lovasz that I mentioned in class. Euler(ian) circuits: [Rosen, Sct. 9.5].
- Eighth (short) week: Hamiltonian cycles/circuits: [Rosen, Sct. 9.5]. Dirac's theorem is proved in [Rosen, Exerc. 65 on page 647] but our proof is slightly different. Planar graphs: [Rosen, Sct. 9.7]. Graph minors are not covered there, see Wikipedia article. Our proof of Euler's formula is inspired by [Rosen, Excerc. 18 on page 665], but notice again an important twist: 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.
- Ninth (short) week: The standard (and excellent) reference for the probabilistic method is The Probabilistic Method by Alon and Spencer. In particular, our result about tournaments is Theorem 1.2.1. 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.
- Tenth (short) week: 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. The growth of functions is [Rosen, Sct. 3.2]. Wikipedia article on iterated algorithm illustrates the point that the log star function is more useful in the analysis of algorithms than you might think.