Discrete Mathematics

10 Aug -- 09 Dec 2011

Class Timings: Wednesday and Friday 11:30 to 13:00

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

Tentative Schedule

• Lecture 1: Introduction -- An Overview and the Josephus Problem.
• Lecture 2: Sums -- Methods to derive closed form for sums (Perturbation method, Using Calculus, and Finite Calculus). Notes
• Lecture 3: Infinite sums and the Basel Problem. Notes
• Lecture 4: Infinity of Primes -- Five proofs. Notes
• Lecture 5: Bertrand's postulate -- Erdos and Ramanujan's proof. Notes.
• Lecture 6-7: Recurrences, Generating functions, Stirling numbers of second kind, Bell numbers, Formal theory of power series. Recurrences. Generating Function.
• Lecture 8: The Principle of Inclusion and Exclusion (PIE), Derangements, Eulers phi function, Using generating functions for PIE. Notes.
• Lecture 9: The Twelvefold Way, and some partitioning of numbers. Notes.
• Lecture 10: Computing the nth partition number. Notes.
• Lecture 11: The Problems des Menages. Notes.
• Lecture 12-13: Graph Theory (Trees, Isomorphism, Enumeration of Rooted and Labelled Trees). Notes.
• Lecture 14-15: Graph Theory (Connectivity of Graphs, Menger's Theorem). Notes.
• Lecture 16-18: Graph Theory (Matching in Bipartite Graphs, Konig's theorem, Hopcroft-Karp Algorithm, Hall's theorem, Tutte's result). Notes.
• Lecture 19-22: Graph Theory (Planarity). Notes.
• Lecture 23: Pigeonhole Principle, Dirichlet's approximation theorem, Monotone subsequences and application to order dimension of a graph. Notes.
• Lecture 24: Probabilistic Method (Tournaments with a winner, Existence of graphs with large chromatic number and girth).
• Lecture 25: Probabilistic Method (Lovasz Local Lemma, Applications to coloring hypergprahs, existence of cycles in simple directed graphs)
• Lecture 26: Discrete Geometry (Some basic definitions, Radon's Lemma, Helly's theorem, Ham-Sandwich).
• Lecture 27: Discrete Geometry (Centerpoint theorem, Fractional Helly's Theorem).
• Lecture 28: Discrete Geometry (Colourful Caratheodory, Tverberg's Theorem, Sarkaria's Proof).
• Lecture 29: Discrete Geometry (Sperner's Lemma and Brouwer's fixed point theorem).

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.