CMSC 27100-1: Discrete Mathematics

Course description

Winter 16: Monday, Wednesday, Friday 9:30am-10:20am (Ryerson 251)

Office hours.

Leonardo Coregliano lenacore@uchicago.edu Theory Lounge Ryerson 162 Monday 10:30am-12pm	Samira Sheikhi samirasheikhi@gmail.com Theory Lounge Ryerson 162 Tuesday 4:30pm-6pm
Alexander Razborov razborov@cs.uchicago.edu Ryerson 257E Wednesday 10:30am-12pm	Kai Li lik11@cs.uchicago.edu Theory Lounge Ryerson 162 Thursday 4pm-5:30pm

Lecture Notes of a few selected lectures are available here. If you find the effort useful, consider volunteering to scribe one lecture among those that will sufficiently deviate from Rosen's textbook.

Homeworks. There will be weekly homework assignments due at the beginning of class each Wednesday. The first set will be released on January 12 or 13 (and due January 20). 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 January 25th
- Midterm 2: Friday February 19th
- Final: Wednesday March 16th, 10:30am-12:30pm, Ry 251

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.
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. S. Jukna, Extremal Combinatorics, Springer-Verlag, 2001.
4. N. Alon, J. Spencer, The Probabilistic Method, Wiley-Interscience, 2008.
5. A. Razborov, Foundations of computational complexity theory, in Surveys in modern mathematics, London Mathematical Society lecture note series, 321, 2005.
6. G. Andrews, K. Erickkson, Integer Partitions, Cambridge University Press, 2004.
7. R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge University Press, 2007.
8. G. Sierksma, H. Hoogeveen, Seven criteria for integer sequences being graphic, Journal of Graph Theory 15, No. 2 (1991) 223–231
9. L. Babai, Graph Isomorphism in Quasipolynomial Time.
10. Z. Furedi, M. Simonovits, The history of degenerate (bipartite) extremal graph problems, in Erdos Centennial, Volume 25 of the series Bolyai Society Mathematical Studies, pp 169-264.
11. B. Barak, G. Kindler, R. Shaltiel, B. Sudakov and A. Wigderson, Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors, Journal of the ACM, Volume 57, Number 4, April 2010.

Progress and references.
- First week: Bezout's Theorem and the Euclidean Algorithm are in [Rosen, Section 4.3], 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. Hall's marriage theorem: [Rosen, Sct. 10.2, Thm. 5]; again, he gives a rigorous mathematical proof. For the algorithmic (augmenting path) proof I recommend to check out [3, Section 5.4] or (if you feel adventurous) [2, Section 7]. 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. For a fun introduction to the fundamentals of complexity theory, see e.g. my article [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. Induction: [Rosen, Sct. 5.1]. Sum-of-Cubes: [Rosen, Sct.5.1, Exc. 4]. Fibonacci numbers: [Rosen, Sct. 2.4, Def. 5]. Binet's formula: [Rosen, Sct. 8.2, Example 4] (I hope to have time to do that kind of stuff more systematically.) Well-ordered sets and transfinite induction: [Rozen, Sct. 9.6, pages 620-622]. 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 Pigeonhole principle: [Rosen, Sct. 6.2] (we'll certainly 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 (short): Binomial Theorem [Rosen, Sct. 6.4]. Inclusion-Exclusion Principle [Rosen, Sct. 8.5] and counting surjective functions [Rosen, Sct, 8.6, Thm. 1]. 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). Multinomial coefficients: [Rosen, Sct. 6.5, Exc. 62 and 63]. The Ball Game [Rosen, pages 428-431] started: we did distinguishable balls vs. distinguishable boxes (nothing new, already familiar numbers).
- Fourth week: Midterm. The Ball Game cntd. Dist. balls vs. Indist. boxes. Equivalence relations: [Rosen, Sct. 9.5]. 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, and an excellent recap of (practically) all the materials, and a bit more, we did in the counting block is called Twelvefold way. Pigeon-Hole-Principle: I recommend to read [Rosen, Sct. 6.2] for more beautiful examples of its application. Dirichlet's approximation theorem: yes, Wikipedia article. Probability spaces and events: [Rosen, Sct. 7.2].
- Fifth week: Conditional probability: [Rosen, Sct. 7.2]. 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 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] 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. 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 (short): Markov's inequality: [Rosen, Exc. 37 on page 493]. Variance and its properties: [Rosen, pages 487-489]. Chebyshev's inequality: [Rosen, page 491]. 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. Basic terminology about subgraphs: [Rosen, pages 663-665]. Adjacency matrices: [Rosen, Sct. 10.3]. Counting paths via adjacency matrices: [Rozen, Sct. 10.4, Theorem 2]. Graph isomorphisms and graph invariants are discussed in [Rosen, Sct. 10.3]. Babai's quasi-polynomial algorithm for graph isomorphism: [9]. Basic terminology about subgraphs: [Rosen, pages 663-665]. 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. Extremal problems for even cycles (and related problems): [10]. Clique number: [Rosen, pages 739-742]. Chromatic number: [Rosen, Sct. 10.8]. Midterm.
- Eighth week: Guest lecturer (Professor Simon). Trees and rooted trees. Equivalent definitions of trees. Spanning trees. Rooted trees, binary trees, computer representations, and traversal algorithms. Polish notation. Caeley's formula (Pitman's proof). Informal definition of planarity (edges are segments on the plane). Jordan curve theorem. 4-color theorem (informally). Euler's formula for plane embeddings. e \leq 3v -6. K_5 is not planar. Subdivisions and Kuratowski's theorem (informally).
- Ninth week: Euler(ian) cycles/circuits: [Rosen, Sct. 10.5], and the main result is [Rosen, Thm. 1 on page 696]. Hamiltonian paths and cycles: [Rosen, Sct.10.5]. An alternate proof of Dirac's theorem and Ore's theorem is given in [Rosen, Exc. 65 on page 707]. 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. In particular, that document contains sketches of some of the missing proofs.
- Tenth week (short): 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. In particular, Sections 2.1 proves our bound on $R(m,n)$, and Section 4 re-caps known lower and upper bounds. CS-style explicit constructions of Ramsey graphs: [11] (the text is challenging!) A standard reference on the probabilistic method in combinatorics is [4]. Our proof of Erdos-Renyi theorem is literally taken from [Rosen, Sct. 7.2, Thm. 4] (it also contains the calculations we skipped in class), and tournaments without small dominanting sets is [Rosen, Sct. 7.2, Exc. 39]. Existence of small dominating sets in graphs with large minimum degree: [4, Theorem 1.2.2].