MA 216: Introduction to Graph Theory
|
Instructor:
|
Arvind Ayyer
|
|
Office:
|
X-15 (new wing)
|
|
Phone number:
|
(2293) 3215
|
|
Email:
|
(First name) at iisc dot ac dot in
|
|
Class Timings:
|
Tuesdays and Thursdays, 5:00–6:30pm.
|
|
Classroom:
|
LH 1, Mathematics Department (first floor)
|
|
Office hours:
|
By appointment
|
|
Textbooks:
|
Graph theory
by Adrian Bondy and U.S.R. Murty
ISBN-13 - 978-1846289699
Graph theory
by Reinhard Diestel
ISBN-13 - 978-3540261827
Introduction to graph theory
by Douglas B. West
ISBN-10 - 0-13-227828-6
|
|
TA:
|
- Subhajit Ghost (gsubhajit at iisc dot ac dot in)
|
Course Prerequisites
Basic linear algebra and some exposure to proofs and abstract mathematics.
Course Description
Graphs, subgraphs, Eulerian tours, trees, matrix tree theorem and Cayley's formula,
connectedness and Menger's theorem, planarity and Kuratowski's theorem, chromatic number
and chromatic polynomial, Tutte polynomial, the five-colour theorem, matchings, Hall's theorem,
Tutte's theorem, perfect matchings and Kasteleyn's theorem, the probabilistic method, basics of algebraic graph theory
Exams
All exams will be closed book, closed notes, and
no calculators or electronic devices are allowed.
No communication among the students will be tolerated.
There will be no make up exams.
Grading
Here are the weights for the homework and exams.
All marks will be posted online
on Moodle.
- 5% – Attendance
- 15% – Homeworks
- 30% – Midterm
- 50% – Final (Nov 30: 2pm - 5pm)
Tentative Class Plan
Week 1 (Aug 6, 8): Sections 1.1-1.2 of B-M
Week 2 (Aug 13): Sections 1.2-1.4 of B-M
Homework 1 is
here and is
due on Aug. 22.
Week 3 (Aug 20, 22): Sections 2.1-2.5, 3.1-3.3 of B-M
Week 4 (Aug 27, 29): Sections 18.1, 18.3, 4.1-4.2 of B-M
Homework 2 is
here and is
due on Sep. 5.
Week 5 (Sep 3, 5): Cayley's theorem, Section 5.1 of B-M
Week 6 (Sep 12): Sections 5.2, 5.3 of B-M
Homework 3 is
here and is
due on Sep. 19.
Week 7 (Sep 17, 19): Sections 7.1-7.2 of B-M
Week 8 : Midsemester exam on Sep 24: 5-6:30pm
Week 9 (Oct 1, 3): Sections 7.3, 9.1 of B-M
Week 10 (Oct 10): Section 9.1 of B-M
Week 11 (Oct 15, 17): Sections 10.1-10.3 of B-M
Week 12 (Oct 22, 24): Sections 10.4-10.5 of B-M
Homework 4 is
here and is
due on Oct. 31.
Week 13 (Oct 29, 31): Sections 16.1-16.3 of B-M
Week 14 (Nov 7): Kasteleyn theory
Week 16 (Nov 19, 21): Section 14.1 of B-M
Final on Nov 30: 2pm - 5pm