### 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.