Discrete Mathematics
08 Aug -- 07 Dec 2025
Class Timings: Tuesday (11:30 to 13:00) and Friday (11:30 to 13:00)
Tentative Schedule
- Lecture 1: Introduction -- An Overview; Recurrences (Domain and Range Transformation). Notes.
- Lecture 2-4: Finite Calculus, Euler-McLaurin Formula. Notes.
- Lecture 5-8: Generating Functions. Notes.
- Lecture 9-11: The Principle of Inclusion and Exclusion (PIE), Derangements, Eulers phi function. Notes
- Lecture 12-14: Mobius inversion on posets. Notes
- Lecture 15-16: Pigeonhole Principle, Dirichlet's approximation theorem, Monotone subsequences and application to order dimension of a graph. Notes
- Lecture 17-19: Ramsey Theory and its applications. Notes
- Lecture 20-21: Basic Discrete Probability and
the Probabilistic method (Tournaments) and Alon's upper bound using permanents.
- Lecture 22-24: Basic Discrete Math (Expectation) and the Probabilistic Method (Existence of graphs with large chromatic number and girth). Notes.
- Lecture 25-30: Probabilistic Method (Turan's result on number of distinct primes -- The Second Moment,Lovasz Local Lemma, Applications to coloring hypergprahs, existence of cycles in simple directed graphs) Notes.
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.
- Stanley: Enumerative combinatorics, both volumes.
- Flajolet, Sdgewick: Analytic Combinatorics.
- Spencer: Asymptopia.
Homework