Home
About me
Education
Experience
Teaching
Publications
Supervision
Contact
Miscellaneous
MA1240/MA5010 Combinatorics/Combinatorics and Graph Theory
Instructor
: M. Rajesh Kannan
Instructor's mail id
: rajeshkannan@math.iith.ac.in
Class Schedule
: Monday - 11 am - 11.55 am, Wednesday - 10 am - 10.55 am, Thursday 9 am - 9.55 am.
Venue
: A 117
Office hours
: By appointment (C-213(G)).
Topics covered
Basics of graphs, isomorphism, trees, Minimum spanning tree, Kruskal's algorithm.
Counting spanning trees, Prufer sequence, Cayley's formula, Matrix-tree theorem (without proof).
Mantel's theorem. Bipartite graphs, Matching, Hall's theorem, System of distinct representatives.
Eulerian graphs, Decompositions, Graham and Pollak theorem, Veblen's theorem.
Hamiltonian graphs, Ore's theorem.
Planer graphs, Euler's formula and its applications.
Chromatic number, Five color theorem.
Basic Counting: sum rule, product rule and inclusion-exclusion principle.
Pigeon hole principle, generalized pigeon hole principle and its applications.
Permutation and Combinations. Permutation and combinations with repetitions, binomial and multinomial coefficients.
Weak compositions, compositions, set partitions, Stirling numbers, Bell numbers. Integer partition, Ferrer's shape, conjugate partitions. Catalan numbers.
Recurrence relations. Solving linear recurrence relations with constant coefficients.
Ordinary generating functions, exponential generating functions. Solving recurrence relations using generating functions.
Text books:
Miklos Bona, A walk through combinatorics,Foruth edition, World Scientific.
Gary Chartrand, Introductory graph theory, Dover.
Richard A. Brualdi, Introductory combinatorics, Fourth edition, Pearson
Problems sheets:
Problem Sheet 1
Problem Sheet 2
Problem Sheet 3
Problem Sheet 4
Problem Sheet 5
Some interesting stuffs:
A tree with cycle