| Course Archives Theoretical Statistics and Mathematics Unit | ||||||||
|
Course: Discrete Mathematics Instructor: Mainak Ghosh Room: Level: Undergraduate Time: Currently offered |
||||||||
|
Syllabus Past Exams Syllabus: 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. Evaluation:
Top of the page Past Exams | ||||||||
Top of the page
| [ Semester Schedule ][ Statmath Unit ] [Indian Statistical Institute] |