Discrete Mathematics
17 Aug -- 07 Dec 2012
Class Timings: Wednesday (9:30 to 11) and Friday (11:30 to 13:00)
Tentative Schedule
- Lecture 1: Introduction -- An Overview.
- Lecture 2: Recurrences. Notes
- Lecture 3: Sums -- Methods to derive closed form for sums (Perturbation method, Using Calculus, and Finite Calculus). Notes
- Lecture 4: Sums -- Euler-McLaurin Formula. Notes
- Lecture 5: Infinite sums and the Basel Problem. Notes
- Lecture 6: Infinity of Primes -- Five proofs. Notes
- Lecture 7: Bertrand's postulate -- Erdos's proof. Notes.
- Lecture 8-10: Generating functions, Stirling numbers of second kind, Bell numbers, Formal theory of power series, Analytic aspects of power series, Unimodality. Notes.
- Lecture 11: The Principle of Inclusion and Exclusion (PIE), Derangements, Eulers phi function, The Problems des Menages. Notes Notes.
- Lecture 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: Graph Theory (Trees, Isomorphism, Enumeration of Labelled Trees). Notes.
- Lecture 16: Graph Theory (Matching -- Tutte's generalization of Hall's theorem). Notes.
- Lecture 17-18: Graph Theory (Connectivity of Graphs, Menger's Theorem). Notes.
- Lecture 19-22: Graph Theory (Planarity). Notes.
- Lecture 23-24: Pigeonhole Principle, Dirichlet's approximation theorem, Monotone subsequences and application to order dimension of a graph, Ramsey Theory. Notes.
- Lecture 25: Probabilistic Method (Tournaments with a winner, Existence of graphs with large chromatic number and girth).Notes.
- Lecture 26: Probabilistic Method (Lovasz Local Lemma, Applications to coloring hypergprahs, existence of cycles in simple directed graphs, Frugal colorings)Notes.
- Lecture 27: Discrete Geometry (Sperner's Lemma, Brouwer's fixed point theorem, Hex game).
- Lecture 28: Discrete Geometry (Borsuk-Ulam 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