Discrete Mathematics

10 Aug -- 17 Dec 2010

Office Hours: Monday and Wednesday 15:30 to 17:00

Schedule

• Lecture 1: Introduction, Various equivalent formulations of principle of induction (weak, strong, total ordering on N, method of inifinite descent), Relations.
• Lecture 2: Definition Equivalence relations, Order relations, Posets, Binomial theorem, Counting sets of size modulo some m, Estimates on factorial (straightforward estimates, AM > GM estimate, based upon calculus).
• Lecture 3: Estimates on binomial coefficient (n choose k), largest binomial coefficient (2n choose n), Erdos's proof of Bertrand's postulate. Notes.
• Lecture 4: The Master Recurrence, Domain and Range transformations, Generalization of the Master theorem (filling the log gap)(result from Brassard and Bratley's book Fundamental Algorithms), the Multiterm Master Recurrence (MMR), Real Induction, The "Master Theorem" for MMR (see Akra-Bazzi, Leighton's note, and Yap's paper). Notes .
• Lecture 5: More recurrence, Generating functions, Stirling numbers of second kind, Bell numbers, Formal theory of power series.
• Lecture 6: The Principle of Inclusion and Exclusion (PIE), Derangements, Eulers phi function, An exact count of number of elements contained in a given index of sets.
• Lecture 7: Using generating functions for PIE, Multisets, Permutations.
• Lecture 8: The Twelvefold Way, and some partitioning of numbers.
• Lecture 9: Algorithms for computing the nth partition number.
• Lecture 10: Latin squares, Bounds on number of Latin squares of a given order, System of Distinct Representatives (various counting versions).
• Lecture 11: Completing Latin squares (Smetaniuk's algorithm).
• Lecture 12: Pigeonhole Principle, Dirichlet's approximation theorem, Monotone subsequences and application to order dimension of a graph, on sums of numbers.
• Lecture 13 and 14: Ramsey Theory and its applications.
• Lecture 15: Discrete Geometry (Some basic definitions, Radon's Lemma, Helly's theorem, Ham-Sandwich).
• Lecture 16: Discrete Geometry (Centerpoint theorem, Fractional Helly's Theorem).
• Lecture 17: Discrete Geometry (Colourful Caratheodory, Tverberg's Theorem, Sarkaria's Proof).
• Lecture 18: Discrete Geometry (Sperner's Lemma and Brouwer's fixed point theorem).
• Lecture 19: Discrete Geometry (Borsuk-Ulam Theorem and its equivalent formulations, Ham-Sandwich Theorem, and Tucker's Lemma).
• Lecture 20: Probabilistic Method (Tournaments with a winner, Existence of graphs with large chromatic number and girth).
• Lecture 21: Probabilistic Method (Lovasz Local Lemma, Applications to coloring hypergprahs, existence of cycles in simple directed graphs)
• Lecture 22-23: Polya's theory of counting, Basic Groups.
• Lecture 24: Error Correcting Codes (Introduction and Bounds on the size of codes).
• Lecture 25: The Fundamental THeorem of Coding Theory -- Shannon's Theorem (from van Lint's book, second chapter).
• Lecture 26: Introduction to Linear Codes, Hamming Codes (Perfectness and Decoding).
• Lecture 27: The Zero-Error capacity/Shannon capacity of a graph (upper and lower bounds, Lovasz's estimate).

References

Books

• Peter Cameron: Combinatorics -- Topics, Techniques, Algorithms.
• J. Matousek and J. Nesetril: Invitation to Discrete Mathematics.
• J.H. van Lint and R.M. Wilson: Combinatorics.
• H. Wilf: Generatingfunctionology.
• M. Aigner and G.M. Ziegler: Proofs from THE BOOK.
• J. Matousek: Lectures in Discrete Geometry.

Papers

• M. Akra and L. Bazzi. On the solution of linear recurrences.
• T. Leighton. Notes on Better Master Theorems for Divide-and-Conquer Recurrences.
• C. Yap. A Real Elementary Approach to the Master Recurrence and Generalizations .

Homework

• Homework 1: Due Date 21 Sept.
• Homework 2: Due Date 08 Dec.