Course Archives Theoretical Statistics and Mathematics Unit
Course: Graph Theory and Combinatorics
Instructor: Shreedhar Inamdar
Room: left side of Audi
Level: Postgraduate
Time: Currently offered
Syllabus
Past Exams


Syllabus:

i) Construction and Uniqueness of Finite Fields, Linear Codes, Macwilliams identity, Finite projective planes, strongly regular graphs and regular 2-graphs. t designs with emphasis on Mathieu designs. Counting arguments and inclusion exclusion principle. Ramsey Theory: graphical and geometric.
ii) Graphs and digraphs, connectedness, trees, degree sequences, connectivity, Eulerian and Hamiltonian graphs, matchings and SDRs, chromatic numbers and chromatic index, planarity, covering numbers, flows in networks, enumeration, Inclusion exclusion, Ramseys theorem, recurrence relations and generating functions.
iii) Time permitting, some of the following topics may be done: (i) strongly regular graphs, root systems, and classification of graphs with least eigenvalue, (ii) Elements of coding theory (Macwilliams identity, BCH, Golay and Goppa codes, relations with designs).

Suggested Texts :
(a) F. Harary, Graph Theory, Addision-Wesley (1969), Narosa (1988).
(b) D. B. West, Introduction to Graph Theory, Prentice-Hall (Indian Edition 1999).
(c) J. A. Bondy and U. S. R. Murthy, Graph Theory and Applications, MacMillan (1976).
(d) H. J. Ryser, Combinatorial Mathematics, Carus Math. Monograph, MAA (1963).
(e) M. J. Erickson, Introduction to Combinatorics, John Wiley (1996).
(f) L. Lovasz, Combinatorial Problems and Exercises, AMS Chelsea (1979).

Evaluation:
Midterm Exam 40 marks
Home Work / Assignment marks
Final Exam 60 marks
Total 100 marks

Top of the page

Past Exams
Top of the page

[ Semester Schedule ][ SMU ] [Indian Statistical Institute]