AIS - Algorithmic Graph Theory (2023)
Speakers and Syllabus
|
Name of the Speaker with affiliation |
No. of Lectures |
Detailed Syllabus |
|
Dr. Ranveer Singh |
03 |
Complexity analysis: Complexity notations, P, NP, Polynomial-time reduction, NP-hard, Approximation Algorithms, Graph Isomorphism, Counting number of spanning trees v/s counting number of perfect matchings. (1. Lab session) |
|
Dr. Nishad Kothari |
06 |
Matching Theory: Ear Decompositions of graphs, tight Cut Decompositions, Lovasz's Uniqueness Theorem, Bricks and Braces and their characterizations, Edmonds-Lovasz-Pulleyblank Theorem, Brick and Brace generation theorems, Pfaffian orientations (algebraic connections), The Perfect Matching Polytope, Edmonds' Linear Inequality Description, Birkhoff-von Neumann graphs, combinatorial diameter, PM-compact graphs, algorithmic implications |
|
Prof. Saket Saurabh |
06 |
Network Flow Algorithms: Basic concepts on network flow, Max-flow mincut theorem, Ford-Fulkerson algorithm, Push-relabel algorithm, Minimum cost flow algorithm, Out-of-kilter algorithm |
|
Prof. Krishnan |
03 |
Distance matrices and their algebraic properties: Graham-Pollak theorem and its generalization to Steiner distances. Four point condition on trees and matrices associated to them. |
|
Dr. Rogers Mathew |
06 |
Container method: The method of hypergraph containers was developed recently (in 2015) by Balogh, Morris and Samotij and, independently, by Saxton and Thomason. Since hypergraphs can model many combinatorial structures, this method has found numerous applications in areas like Ramsey theory, extremal graph theory, discrete geometry, etc. Apart from aiding in proving enumerative and structural results, the method has been found useful in bounding the number of finite objects that forbid certain substructures. For example, (i) counting the maximum number of edges an Erdos-Renyi random graph can have with high probability if it is triangle-free or (ii) counting the number of Sidon sets in [n], etc. In these lectures, we will explain the container method and shall try to demonstrate as many applications of it as possible. |
|
Prof. R B Bapat |
06 |
Spectral Graph Theory: Adjacency matrix, Laplacian Matrix, Algebraic Connectivity, Fiedler vector, Algebra of regular graphs, Strongly regular graphs and Friendship theorem. |
|
Dr. Rajesh Kannan |
06 |
Expander and Ramanujan Graphs: Normalized Laplacian matrices, Cheegers's inequality, Expansion coefficient, Expander mixing lemma, Random walks on graphs, stationary distribution, mixing time, Expander graphs and Ramanujan Graphs. |
References:
- D. B. West: Introduction to Graph Theory: Pearson Education: India : 2015: 8178088304.
- R. Diestel: Graph Theory: Springer-Verlag: New York: 2000: 0387950141.
- R.B. Bapat: Graphs and matrices: Springer. : London: 2010: 9789380250694.
- Bondy and U. S. R. Murthy: Graph Theory, Graduate Texts In Mathematics: Springer : Switzerland: 2008: 978-1-84628-969-9.
- Alan Gibbons : Algorithmic Graph Theory: Cambridge University Press: 1985: 9780521288811.
Time Table
Time-Table
(with names of speakers and course associates/tutors)
|
Day |
Date |
Lec 1 9.30 |
Tea 11.05 |
Lec 2 11.30 |
Lunch 1.05 |
Tut 2.30 |
Tea 3.35 |
Tut 4.00 |
Snacks 5.05 |
|
|
|
(Name of the speaker) |
|
(Name of the speaker) |
|
(Name of the speaker + tutors) |
|
(Name of the speaker + tutors) |
|
|
Mon |
26-06-2023 |
Dr. Ranveer Singh |
|
Dr. Ranveer Singh |
|
Dr. Ranveer Singh + Mr. Hitesh Wankhede |
|
Dr. Ranveer Singh + Mr. Hitesh Wankhede |
|
|
Tues |
27-06-2023 |
Dr. Ranveer Singh |
|
Dr. Nishad Kothari |
|
Dr. Ranveer Singh + Mr. Hitesh Wankhede |
|
Dr. Nishad Kothari + Mr. Amit Kumar Mallik |
|
|
Wed |
28-06-2023 |
Dr. Nishad Kothari |
|
Dr. Nishad Kothari |
|
Dr. Nishad Kothari + Mr. Amit Kumar Mallik |
|
Dr. Nishad Kothari + Mr. Amit Kumar Mallik |
|
|
Thu |
29-06-2023 |
Dr. Nishad Kothari |
|
Dr. Nishad Kothari |
|
Dr. Nishad Kothari + Mr. Amit Kumar Mallik |
|
Dr. Nishad Kothari + Mr. Amit Kumar Mallik |
|
|
Fri |
30-06-2023 |
Dr. Nishad Kothari |
|
Prof. Saket Saurabh |
|
Dr. Nishad Kothari + Mr. Amit Kumar Mallik |
|
Prof. Saket Saurabh + Dr. Pradumn Pandey |
|
|
Sat |
01-07-2023 |
Prof. Saket Saurabh |
|
Prof. Saket Saurabh |
|
Prof. Saket Saurabh + Dr. Pradumn Pandey |
|
Prof. Saket Saurabh + Dr. Pradumn Pandey |
|
|
SUNDAY: OFF |
|||||||||
|
Mon |
03-07-2023 |
Prof. Saket Saurabh |
|
Prof. Saket Saurabh |
|
Prof. Saket Saurabh + Dr. Pradumn Pandey |
|
Prof. Saket Saurabh + Dr. Pradumn Pandey |
|
|
Tues |
04-07-2023 |
Prof. Saket Saurabh |
|
Dr. Rogers Mathews |
|
Prof. Saket Saurabh + Dr. Pradumn Pandey |
|
Dr. Rogers Mathews + Miss. Shiwali |
|
|
Wed |
05-07-2023 |
Dr. Rogers Mathews |
|
Dr. Rogers Mathews |
|
Dr. Rogers Mathews + Miss. Shiwali |
|
Dr. Rogers Mathews + Miss. Shiwali |
|
|
Thu |
06-07-2023 |
Dr. Rogers Mathews |
|
Dr. Rogers Mathews |
|
Dr. Rogers Mathews + Miss. Shiwali |
|
Dr. Rogers Mathews + Miss. Shiwali |
|
|
Fri |
07-07-2023 |
Dr. Rogers Mathews |
|
Prof. Krishnan |
|
Dr. Rogers Mathews + Miss. Shiwali |
|
Prof. Krishnan + Mr. Rakesh Jana |
|
|
Sat |
08-07-2023 |
Prof. Krishnan |
|
Prof. Krishnan |
|
Prof. Krishnan + Mr. Rakesh Jana |
|
Prof. Krishnan + Mr. Rakesh Jana |
|
|
SUNDAY: OFF |
|||||||||
|
Mon |
10-07-2023 |
Prof. RB Bapat |
|
Prof. RB Bapat |
|
Prof. RB Bapat + Dr. Shivani Goel |
|
Prof. RB Bapat + Dr. Shivani Goel |
|
|
Tues |
11-07-2023 |
Prof. RB Bapat |
|
Prof. RB Bapat |
|
Prof. RB Bapat + Dr. Shivani Goel |
|
Prof. RB Bapat + Dr. Shivani Goel |
|
|
Wed |
12-07-2023 |
Prof. RB Bapat |
|
Prof. RB Bapat |
|
Prof. RB Bapat + Dr. Shivani Goel |
|
Prof. RB Bapat + Dr. Shivani Goel |
|
|
Thu |
13-07-2023 |
Dr. Rajesh Kannan |
|
Dr. Rajesh Kannan |
|
Dr. Rajesh Kannan + Mr.Iswar Mahato |
|
Dr. Rajesh Kannan + Mr.Iswar Mahato |
|
|
Fri |
14-07-2023 |
Dr. Rajesh Kannan |
|
Dr. Rajesh Kannan |
|
Dr. Rajesh Kannan + Mr.Iswar Mahato |
|
Dr. Rajesh Kannan + Mr.Iswar Mahato |
|
|
Sat |
15-07-2023 |
Dr. Rajesh Kannan |
|
Dr. Rajesh Kannan |
|
Dr. Rajesh Kannan +Mr.Iswar Mahato |
|
Dr. Rajesh Kannan +Mr.Iswar Mahato |
|
Tutorial Assistants:
|
S. No. |
Name |
Affiliation |
|
1 |
Mr. Rakesh Jana |
IIT Bombay |
|
2 |
Mr. Hitesh Wankhede |
IIT Indore |
|
3 |
Dr. Shivani Goel |
IISc Banglore |
|
4 |
Miss. Shiwali |
IIT Hyderabad |
|
5 |
Mr. Amit Kumar Mallik |
IIT Bombay |
|
6 |
Dr. Pradumn Pandey |
IIT Roorkee |
|
7 |
Mr. Iswar Mahato |
IIT Hyderabad |