Top

- Assignment 1 (due on September 5th in class, no extensions): Problems 1.1.30, 1.1.38, 1.3.13, 1.4.29, 1.4.38 from D.B.West
- Assignment 2 (extended version) (due on November 6th, no extensions, no discussion or online reference allowed, you are welcome to talk to me if you are stuck) (For the first assignment problem, this reference could be useful.)
- Quiz 1
- Quiz 2
- Midsem
- Endsem

- Aug 8: Graph theory: Introduction, simple results related to connectivity, degrees of vertices (Ref: Chapter 1 of D.B. West's book)
- Aug 11: Trees, Bipartite graphs, Mantel's theorem, Eulerian circuits, Directed graphs
- Aug 18: Tournaments, Matchings: Augmenting paths, Berge's theorem (Chapter 3 of D B West's book)
- Aug 22: Hall's theorem, König-Egerváry theorem (Chapter 3 from D B West's book)
- Aug 29: Planar graphs: Introduction, Euler's formula, characterization, coloring (Ref: Relevant topics from Chapter 6 of D B West's book)
- Sept 11: Tutte's theorem (Ref: D B West's book)
- Sept 5: Pigeonhole principle, counting: permutations combinations, cardinalities of sets (Ref: These notes and Sections 1.1-1.3, 1.5, 1.6 of this book)
- Sept 8: Erdös-Szekeres theorem, Principle of inclusion-exclusion
- Sept 12: Derangementes, Generating functions: partitions (Ref: Roberts, Tesman book)
- Sept 15: Recurrence relations: Regions in plane, generalized binomial coefficients, solving linear recurrence relations with constant coefficients, derangements using exponential generating functions (Ref: Roberts-Tesman book)
- Sept 19: Catalan numbers (number of simple, ordered, rooted trees), Combinatorics of sets: Sperner's theorem (Ref: Robert-Tesman book, Anderson's book)
- Sept 22: Posets, Dilworth's theorem (Ref: Anderson's book)
#### Module 3: Algebra (Ref: Topics in Algebra by Herstein)

Sept 22: Groups: Definition, basic properties, subgroups, cosets, Lagrange's theorem, Fermat's little theorem, cyclic groups - Oct 3: Homomorphisms, normal subgroups, quotient groups
- Oct 6: Permutation groups, Cayley's theorem, cycle structure and sign of permutations, uniqueness of sign, Sylow's theorem (without proof), Direct product and fundamental theorem on finite abelian groups (without proof)
- Oct 9: Rings and Fields: Definition and examples, integral domain, ideals, properties of finite fields, polynomial rings, construction of finite fields from polynomial rings
- Oct 13: Construction of finite fields continued, Vector spaces: definition, dimension, linear independence and basis
- Oct 24: Vector spaces, inner product, Cauchy-Schwartz inequality, linear transformations, rank-nullity theorem, orthogonality (Ref: Artin's book)
- Oct 27: Linear algebra continued: Matrices and system of linear equations, determinant, characteristic polynomial, eigenvalues and eigenvectors
- Nov 4: Definitions and basic formulae: Sample space, events, conditional probability, examples [SR]
- Nov 6: Independent events, random variables and expectation, discrete random variables: Bernoulli, Binomial, Introduction to probabilistic method: 2-edge-coloring of an n-clique with no monochromatic k-clique [SR]
- Nov 7: Discrete random variables: Poisson, Geometric, Negative binomial, Applications: Coupon collector's problem [MR], probabilistic method: maximum number of Hamiltonian paths in a tournament, Maximum likelihood estimate [SR]
- Nov 10: Continuous random variables: uniform, Gaussian, exponential. Probability density function and cumulative distribution function, expectation, variance.
- Nov 13: Joint distribution, independence, Markov's inequality
- Nov 14: Covariance, Chebyshev's inequality [SR], Chernoff bounds (Ref). Example: Hat matching
- Nov 4: Group action, orbit-stabilizer theorem, Burnside's lemma, examples: colorings of chessboard, colorings of faces of a cube (Ref: Alon-Slomson's book)
- Nov 17: Markov chains: Irreducibility, aperiodicity, stationary distribution. Example: Random walks in regular, undirected graphs (Ref)
- Nov 20: Random walks continued, Introduction to coding theory: Entropy, prefix-codes
- Nov 21: Introduction to coding theory continued: Noiseless coding theorem, Noisy coding theorem, Huffman codes, Hamming codes, Reed-Solomon codes