Discrete Mathematics
14 Aug -- 07 Dec 2018
Class Timings: Tuesday (11:30 to 13:00) and Thursday (11:30 to 13:00)
Tentative Schedule
- Lecture 1: Introduction -- An Overview; Recurrences. Notes
- Lecture 2: Sums -- Methods to derive closed form for sums (Perturbation method, Using Calculus, and Finite Calculus). Notes
- Lecture 3: Sums -- Euler-McLaurin Formula. Notes
- Lecture 4: Infinite sums and the Basel Problem. Notes
- Lecture 5: Generating functions, Stirling numbers of second kind, Bell numbers.Notes.
- Lecture 6: Theory of formal power series. Notes.
- Lecture 7: Unimodality I. Notes.
- Lecture 8,9: Analytic aspects of power series. Notes.
- Lecture 10: The Principle of Inclusion and Exclusion (PIE), Derangements, Eulers phi function, The Problems des Menages. Notes Notes.
- Lecture 11-12: The Principle of Inclusion and Exclusion (PIE) via Generating functions and via linear algebra, Rook Polynomials. Notes
- Lecture 13-14: Mobius inversion on posets. Notes
- Lecture 15: Unimodality II. Notes.
- Lecture 16-17: Graph Theory (Trees, Isomorphism, Enumeration of Labelled Trees). Notes.
- Lecture 18: Graph Theory (Matching -- Tutte's generalization of Hall's theorem). Notes.
- Lecture 18-19: Graph Theory (Connectivity of Graphs, Menger's Theorem). Notes.
- Lecture 20-23: Graph Theory (Planarity). Notes.
- Lecture 24-25: Pigeonhole Principle, Dirichlet's approximation theorem, Monotone subsequences and application to order dimension of a graph, Ramsey Theory. Notes.
- Lecture 26-27: Szemeredi's Regularity Lemma and its Applications.
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.
Homework