MA 217: Discrete Mathematics
Combinatorics: Basic counting techniques. Principle of inclusion and exclusion.
Recurrence relations and generating functions. Pigeon-hole principle, Ramsey
theory. Standard counting numbers, Polya enumeration theorem.
Graph Theory: Elementary notions, Shortest path problems. Eulerian and
Hamiltonian graphs, The Chinese postman problem. Matchings, the personal
assignment prolem. Colouring or Graphs.
Number Theory: Divisibility Arithmetic functions. Congruences. Diophantine
equations. Fermat’s big theorem, Quadratic reciprocity laws. Primitive roots.
Suggested books and references:
Bondy, J. A. and Muirty, U. S. R., Graph theory with applications, Elsevier-North Holland, 1976.
Burton, D., Elementary Number Theory, McGraw Hill, 1997.
Clark, J. and Holton, D. A., A first book at Graph Theory, World Scientific Cp., 1991.
Polya G. D., Tarjan, R. E. and Woods, D. R., Notes on Introductory Combinations, Springer-Verlag, 1990.
+91 (80) 2293 2711, +91 (80) 2293 2265 ; E-mail: chair.math[at]iisc[dot]ac[dot]in
Last updated: 20 Feb 2020