CMSC 27100-1: Discrete Mathematics

Course description

Autumn13: Monday, Wednesday, Friday 1:30pm-2:20pm (Harper 140)

Office hours.

Alexander Razborov
razborov@cs.uchicago.edu
Ryerson 257E (or near the lecture room, depending on demand)
Monday 2:30pm-3:30pm and by appointment

Yuan Li
jsliyuan@gmail.com
Ryerson 162B
Tuesday 9am-10:30am

Denis Pankratov
denis.pankratov@gmail.com
Ryerson 162A
Friday 5pm-6:30pm

Lecture Notes of some selected lectures are available here.

Homeworks. There will be weekly homework assignments due at the beginning of class each Wednesday. The first set will be released on October 9 (and due October 16). You are allowed to work together on solving homework problems, but 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 -- this is the way to tell apart joint work from plagiarism!

Exams. There will be two midterms and a final.

Midterm 1: Monday Oct. 21th
Midterm 2: Friday Nov. 15th
Final: Wednesday December 11th

Literature. We will follow Discrete Mathematics and Its Applications (7th Edition) by K. Rosen. It should be available at the Seminary co-op, and it should be on reserve in the math library.
Some more advanced books covering a subset of our topics are listed below. The list will be updated as we are making progress.

J. Matousek, J. Nesetril, An Invitation to Discrete Mathematics, Oxford University Press, 2009.
L. Lovasz, Combinatorial Problems and Exercises, AMS Chelsea Publishing, 2007.
S. Jukna, Extremal Combinatorics, Springer-Verlag, 2001.
N. Alon, J. Spencer, The Probabilistic Method, Wiley-Interscience, 2008.
A. Razborov, Foundations of computational complexity theory, in Surveys in modern mathematics, London Mathematical Society lecture note series, 321, 2005.
G. Andrews, K. Erickkson, Integer Partitions, Cambridge University Press, 2004.
R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge University Press, 2007.
G. Sierksma, H. Hoogeveen, Seven criteria for integer sequences being graphic, Journal of Graph Theory 15, No. 2 (1991) 223–231

Progress and references.

First week: Bezout's Theorem is in [Rosen, Section 4.3] (we did only its partial case gcd(a,b)=1), and you may also want to check out [Rosen, Exercise 36 to Sct. 5.2] to see how the same argument looks in the consistently mathematical notation. The augmenting path algorithm for the matching problem: [3, Section 5.4], notice how the author alternates between a rigorous proof and an informal explanation. 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). For an initial information about MaxCut (the football players problem) you can consult this Wikipedia article, and among the sources given therein Newman's article in Encyclopedia of Algorithms looks more accessible. Our approach to finding a ``local'' minimum in this problem is known as Asynchronous Hopfield Network; if you venture into that article, note that $w_{ij}$s are always 0 or 1, and the thresholds $\theta_i$ are always zeros in our case. The 1000* problem is about the behavior of the synchronous case (ibid). The Halting Problem: [Rosen, pages 201-202], we stayed very close on the path (which, though, for a good reason is designated as ``slippery'' in the book). For a highly introductory lecture on the fundamentals of complexity theory, see e.g. [5]. 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 also echoed at the end of [Rosen, Sct. 3.3].

Second week: Discussion about running time and P vs. NP continued. 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 and surjective functions: [Rosen, Sct. 2.3]. The digression about infinite sets is actually the Cantor-Bernstein Theorem; note that in class instead of an injective function from B to A I was talking about a surjective function from A to B. It is easy to construct the former from the latter using Axiom of Choice (how?), but it well might turn out that my statement, unlike the Cantor-Bernstein Theorem, is simply equivalent to the axiom of choice. The Pigeonhole principle: [Rosen, Sct. 6.2] (but we'll return to that). 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].

Third 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). Inclusion-Exclusion Principle [Rosen, Sct. 8.5] and counting surjective functions [Rosen, Sct, 8.6, Thm. 1]. Multinomial coefficients: [Rosen, Sct. 6.5, Exc. 62 and 63]. The Ball Game [Rosen, pages 428-431] started: we did Dist. balls vs. Dist. boxes (nothing new, familiar objects) and Dist. balls vs. Indist. boxes. Equivalence relations: [Rosen, Sct. 9.5].

Fourth week: Midterm. The Ball Game cntd. Indist. balls vs. Dist. boxes: [Rosen, pages 429-430]. Indist. balls vs. Indist. boxes: [Rosen, page 431]. There are whole books (like [6]) entirely devoted to integer partitions. Pigeon-Hole-Principle: again, I recommend to read [Rosen, Sct. 6.2] for more beautiful examples of its application. Dirichlet's approximation theorem: yes, Wikipedia article. Probability spaces, events and conditional probability: [Rosen, Sct. 7.2].

Fifth week: Independent events: [Rosen, pages 457-458]. Bayes' Theorem is covered in [Rosen, Sct. 7.3] (and in many more details than we did in the class). You can read about the controversy surrounding it in this thought-provoking article. The formula of complete probability is not explicit in Rosen's book, but it appears in the proof of [Rosen, Sct. 7.3, Thm. 1] (I should admit it was my primary reason to talk about the Bayesian law at all :-) ) Mutually independent events: [Rosen, Def. 5 on page 458]. Random variables: [Rosen, pages 460-461]. Binomial Distribution: [Rosen, pages 458-460] and the Geometric Distribution: [Rosen, pages 484-485]. 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. Expectations and their linearity: [Rosen, Sct. 7.4]. Independent random variables and product of their expectations: [Rosen, pages 485-487].

Sixth week: Markov's inequality: [Rosen, Exc. 37 on page 493]. Variance and its properties: [Rosen, pages 487-489]. Chebyshev's inequality: [Rosen, page 491]. Bienayme's formula: [Rosen, Sct. 7.4, Thm. 7]. Hashing is marginally touched upon in [Rosen, pages 287-288 and pages 462-463], but randomized (and, in particular, universal) hashing is not discussed in the textbook. Check out Wikipedia article or, for more comprehensive treatment, [7, Sct. 8.4]. Our light version of Chernoff's inequality and its proof is borrowed from a Wikipedia article (see also [7, Theorem 4.1]). Many more interesting (and much more sophisticated) "sharp concentration" bounds can be found in [4]. Graphs and degrees: [Rosen, Sct. 10.2] (Handshaking Theorem is [Rosen, Sct. 10.2, Thm.1]). The original paper by Erdos and Gallai (characterization of degree sequences) is in Hungarian. If you can not read it, you can check out [8]. More material on degree sequences can be found in [Rosen, Exerc. 36-47 on page 667].

Seventh week: 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]. As in many other cases, the Wikipedia article is a good referral point for Moore graphs. 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. Midterm.

Eighth week: Basic terminology about subgraphs: [Rosen, pages 663-665]. Graph isomorphisms and graph invariants are discussed in [Rosen, Sct. 10.3]. 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. Clique and independence number: [Rosen, pages 739-742]. 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, pages 656-658]; for more information (including our criterium) see Wikipedia article. Chromatic number: [Rosen, Sct. 10.8]. Ramsey numbers: [Rosen, pages 404-405]; our simple ($n=6$) bound is [Rosen, Example 13 on page 404]. Wikipedia article on Ramsey numbers is very good and informative; see in particular Sections 2.1 [Proof: 2-color case] and Section 4 [Asymptotics]. Our proof of Erdos-Renyi theorem is literally taken from [Rosen, Sct. 7.2, Thm. 4], and a standard reference on the subject of further applications of the probabilistic method in combinatorics is [4].

Ninth week (short): Euler(ian) cycles/circuits: [Rosen, Sct. 10.5], and the main result is [Rosen, Thm. 1 on page 696] (his proof is algorithmic, this is what I alluded to in class). Hamiltonian cycles: [Rosen, Sct.10.5]. Dirac's theorem (actually, even a stronger statement) is proved in [Rosen, Exc. 65 on page 707]. Planar graphs: [Rosen, Sct. 10.7]. Kuratowski's Theorem: [Rosen, pages 724-725] Graph minors are not covered there, see Wikipedia article on minors. You can read about the colorful history of the four color theorem on [Rosen, page 728]. Our proof of Euler's formula is inspired by [Rosen, Exc. 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. This is the P vs. NP page that I mentioned during one of our numerous digressions.

Tenth week (short): Monte-Carlo methods (and two more examples): [Rosen, pages 463-465]. Note that he says "unknown" when we say "no" and allow errors. Although these two approaches are equivalent, I believe that ours conforms better to the modern literature on the subject. Polynomial Identity Testing (along with the mathematical background I mentioned in class) is in the Wikipedia article on Schwartz-Zippel lemma. As I warned in class, I am 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.