Course Archives Theoretical Statistics and Mathematics Unit
Course: Discrete Mathematics
Level: Undergraduate
Time: Currently not offered
Past Exams


i) BASIC COUNTING TECHNIQUES: Double-counting, Averaging principle, Inclusion- Exclusion principle. Euler indicator, Mobius function and inversion formula. Recursions and generating functions.
ii) PIGEONHOLE PRINCIPLE: The Erdos-Szekeres theorem. Mantels theorem. Turans theorem, Dirichlets theorem, Schurs theorem, Ramsey theory.
iii) GRAPHS: Eulers theorem and Hamilton Cycles. Spanning Trees. Cayleys theorem and Spanning trees.
iv) SYSTEMS OF DISTINCT REPRESENTATIVES: Halls marriage theorem, Applications to latin rectangles and doubly stochastic matrices, Konig-Egervary theorem, Dilworths theorem, Sperners theorem.
v) FLOWS IN NETWORKS: Max-flow min-cut theorem, Ford-Fulkerson theorem, Integrality theorem for max-flow.
vi) LATIN SQUARES AND COMBINATORIAL DESIGNS: Orthogonal Latin squares, Existence theorems and finite projective planes. Block designs. Hadamard designs, Incidence matrices. Steiner triple systems.

Reference Texts:

(a) S. Jukna: Extremal Combinatorics.
(b) J. H. van Lint & R. M. Wilson: A Course in Combinatorics.
(c) D. B. West: Introduction to Graph Theory.
(d) R. A. Beeler: How to Count: An Introduction to Combinatorics and Its Applications.
(e) H. J. Ryser: Combinatorial Mathematics.

Midterm 40 marks
Final Exam 60 marks
Total 100 marks

Top of the page

Past Exams

Top of the page

[ Semester Schedule ][ Statmath Unit ] [Indian Statistical Institute]