Algorithmic Graph Theory (2023) | National Centre for Mathematics

Convener(s)


Name:	Prof. Saket Saurabh	Dr. Ranveer Singh
Mailing Address:	Professor Theoretical Computer Science, IMSc Taramani, Chennai 600 113 Tamil Nadu, India.	Assistant Professor, Department of Computer Science & Engineering, Indian Institute of Technology Indore, POD 1A, Simrol, Khandwa Road, Indore 453552
Email:	saket at imsc.res.in	ranveer at iiti.ac.in

This course deals with theory and algorithms on some advanced topics in graph theory. The first part will cover a brief introduction to the hardness of graph problems and some approximation algorithms. The second part is devoted to matching theory. The third part will cover theory and algorithms on network flows. The fourth part will cover the hypergraph containers. The fifth and sixth part will cover algebraic graph theory.

Dates:

Monday, June 26, 2023 - 09:00 to Saturday, July 15, 2023 - 18:00

Venue:

Venue Address:

Department of Computer Science & Engineering,
Indian Institute of Technology Indore,
Simrol, Khandwa Road, Indore 453552

Venue State:

Madhya Pradesh

Venue City:

Indore

PIN:

453552

Syllabus:

Name of the Speaker with affiliation	No. of Lectures	Detailed Syllabus
Dr. Ranveer Singh IIT Indore	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 IIT Madras	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 IMSC	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 IIT Bombay	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 IIT Hyderabad	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 ISI Delhi	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 IIT Hyderabad	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 to 11.00	Tea 11.05 to 11.25	Lec 2 11.30 to 1.00	Lunch 1.05 to 2.25	Tut 2.30 to 3.30	Tea 3.35 to 3.55	Tut 4.00 to 5.00	Snacks 5.05 to 5.30
		(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

Selected Applicants:

Sr. No.	SID	Full Name	Gender	Affiliation	Position in College/ Univ	Univ/ Inst BA/BSc/BTech/BE/BS.	Univ/Inst M.Sc./M.A.	Year of Passing M.Sc. / M.A
1	47736	Mr. Santhosh Raghul G S	Male	Indian Institute of Technology Madras	PhD	Indian Institute of Information Technology, Design and Manufacturing, Kancheepuram
2	47774	Mr. Akash M	Male	IIT MADRAS	PhD	Anna University BE	Anna University ME	2021
3	47997	Mr. Ravindra Kuber Pawar	Male	BITS Pilani KK Birla Goa Campus	PhD	SPPU, Pune BSc	SPPU Pune MSc	2016
4	48015	Mr Santanu Mandal	Male	NIT Rourkela	PhD Scholar	Vidyasagar University	Vidyasagar University	2014
5	48017	Ms. Pallabi Manna	Female	NIT Rourkela	PhD Scholar	University of Calcutta	University of Calcutta	2015
6	48064	Mr. Koustav De	Male	IIT Kharagpur	PhD Student	Maulana Abul Kalam Azad University of Technology(Formerly known as West Bengal University of Technology) B. Tech	NIT Agartala M. Tech	2020
7	48222	Ms. Santhini K A	Female	IIT Madras	PhD student	Cochin University of Science and Technology Btech	Cochin University of Science and Technology MTech	2014
8	48224	Mr. Keshav Ranjan	Male	IIT Madras	PhD Student	Sant Longowal Institute of Engineering and Technology, Longowal, Sangrur, Punjab (BE)	IIT Patna
9	48294	Dr. Pawan Kumar	Male	Indira Gandhi National Open University	Assistant Professor	Dayalbagh Educational Institute, Agra	Indian Institute of Technology, Delhi	2008
10	48378	Mr. Sonu Verma	Male	South Asian University	M.Sc Student	Christ Church PG College , Kanpur	South Asian University, New Delhi	Appeared / Awaiting Result
11	48257	Mr. Randhir Singh	Male	Department Of Mathematics	Ph.D. Student	BSc.	Department of Mathematics, Savitribai Phule Pune University.	2021
12	48283	Mr Rajat Adak	Male	Indian Institute of Technology Hyderabad	MSc Student	Chennai Mathematical Institute	Indian Institute of Technology Hyderabad	Appeared / Awaiting Result
13	48307	Ms. Pragya Verma	Female	Indian Institute of Technology Hyderabad	MSc Student	Bundelkhand University, Jhansi	Indian Institute of Technology Hyderabad	Appeared / Awaiting Result
14	48328	Ms Shivani Chauhan	Female	Shiv Nadar University	PhD	BSc	MSc	2017
15	48356	Ms Kritika Kashyap	Female	Indian Institute of Technology Palakkad	M.Tech Student	Cotton University	Tezpur University	2021
16	48387	Mr. Nithin K	Male	NATIONAL INSTITUTE OF TECHNOLOGY KARNATAKA	PhD Student.	Kannur University	Kannur University	2017
17	48450	Ms. Vaishali Sharma	Female	Indian Institute of Technology (Indian School of Mines) Dhanbad	PhD	BSc	M.Sc.	2022
18	48456	Ms Saraswati Girish Nanoti	Female	Indian Institute of Technology Gandhinagar	PhD Student	Indian Institute of Technology Roorkee (Integrated MSc)	Indian Institute of Technology Roorkee (Integrated MSc)	2018
19	48597	Mr. Neelabjo Shubhashis Choudhury	Male	Indian Institute of Technology, Kanpur	PhD	Jadavpur University	University of Minnesota, Twin Cities.	2015
20	48604	Ms. Kirti Sahu	Female	National Institute of Technology Rourkela	PhD	Ranchi University	National Institute of Technology Rourkela	2019
21	48913	Mr Rohit Prashanth Vasishta	Male	Ashoka University	Student	Ashoka University	Not Applicable
22	49301	Dr. Deepu Benson	Male	Indian Institute Of Technology Gandhinagar	Research Associate	Vimal Jyothi Engineering College, Kannur University	M.E., Government College of Technology Coimbatore, Anna University	2009
23	49354	Mr. Abhay Jayarajan	Male	Indian Institute of Technology	PhD	Savitribai Phule Pune University BSc	Savitribai Phule Pune University M.Sc.	2022
24	49373	Mr. Rahul Roy	Male	Indian Institute of Technology, Hyderabad	M.Sc Student	VIDYASAGAR UNIVERSITY	Indian Institute of Technology, Hyderabad	Appeared / Awaiting Result
25	49410	Ms. Shiwali Shiwali	Female	IIT Hyderabad	PhD	BTech	NA
26	49510	Ms Kadali Kranthi Priya	Female	Indian Institute of Technology	PhD	Pondicherry central university	Pondicherry central university	2019
27	49570	Dr. Gargi Lather	Female	Indian Institute of Technology Madras	Institute Postdoctoral Fellow	University of Delhi	Indian Institute of Science Education and Research Mohali	2022
28	49582	Mr T I Darsan	Male	Indian Institute of Science Education and Research (IISER)	BS-MS degree (MSc student)	Indian Institute of Science Education and Research (IISER), Pune	Indian Institute of Science Education and Research (IISER), Pune	Appeared / Awaiting Result
29	49594	Ms Karthika D	Female	Rajalakshmi Institute of Technology, Anna University	PhD Student	Bharathiar University	Bharathidasan University	2016
30	49602	Mr. Kousik Samanta	Male	TCG CREST	PhD	Presidency University	Calcutta University	2020
31	49629	Ms. Aditi Howlader	Female	IIT Madras	Post Doctorate Fellow	Ranaghat College	University of Kalyani	2014
32	49675	Mr. Pawan Kumar Nagal	Male	Indian nstitute of Technology Palakkad	PhD	Dayanand College,Hisar	Kurukshetra University	2018
33	49708	Ms Samapti Pratihar	Female	Indian Institute of Technology Madras	PhD	Midnapore College (Autonomous)	National Institute of Technology Rourkela	2022
34	48088	Ms Akankshya Sahu	Female	BITS Pilani, Hyderabad Campus	Ph.D	B.Sc	UNIVERSITY OF HYDERABAD	2020
35	48436	Mr. Aditya Jain	Male	IISER Mohali	MSc. Student	IISER Mohali	IISER Mohali	Appeared / Awaiting Result
36	48503	Ms. Manideepa Saha	Female	Presidency University	PhD	West Bengal State University	University of Calcutta	2014
37	49103	Ms Divyadevi Thangaraj	Female	National Institute of Technology Tiruchirappalli	Ph. D	Seethalakshmi Ramaswami College, Trichirappalli (Bharathidasan University)	Bharathidasan University	2017
38	49278	Mr. Milton Saha	Male	Savitribai Phule Pune University	PhD Student	Presidency University, Kolkata	Savitribai Phule Pune University	2020
39	49692	Mr Samiron Parui	Male	Indian Institute of Science Education and Research Kolkata	PhD	University of Calcutta	University of Calcutta	2014
40	48418	Mr. Sauvik Poddar	Male	Presidency University	PhD Student	St. Xavier's College, Kolkata (Autonomous), BSc	Presidency University, M.Sc.	2021
41	48485	Ms Purna Dutta	Female	Indian Institute of Science Education and Research (IISER) Berhampur	Integrated BS-MS 4th year student	IISER Berhampur	IISER Berhampur	Appeared / Awaiting Result
42	48529	Dr. Lakshmi Lavanya Ramamurthy	Female	Indian Institute of Science Education and Research (IISER) Tirupati	Assistant Professor	University of Madras	University of Madras	2005
43	49518	Ms. Supraja D K	Female	Indian Institute of Technology Dharwad	PhD student	National Degree College, Jayanagar, Bangalore. - BSc	Christ deemed to be University, Bangalore - MSc	2018
44	49193	Ms. Sakshi Ajit Jain	Female	Savitribai Phule Pune University.	Ph.D. Student	BSc	M.Sc.	2022
45	47931	Mr. Kaustav Paul	Male	IIT Ropar	PhD	BSc	MSc	2020
46	48083	Mr Ayyanar K	Male	National Institute of Technology	Ph.D
47	48081	Ms Nithya Muraleedharan	Female	National Institute of Technology Karnataka, Surathkal	PhD (Graph Theory)
48	48114	Mr. Bharadwaj B	Male	National Institute of Technology Karnataka	Ph.D (Graph Theory)
49	48282	Mr. Firdous Ee Jannat	Male	Tezpur University, Napaam, Assam	PhD
50	48383	Ms. Monalisha Sharma	Female	Tezpur University	Ph.D.
51	48736	Mr. Sachin Somra	Male	SOUTH ASIAN UNIVERSITY
52	48783	Mr. Sandeep Kumar	Male	South Asian University
53	48541	Ms Anjitha Ashokan	Female	NATIONAL INSTITUTE OF TECHNOLOGY CALICUT	PhD
54	47558	Mr Prasad Pradeeprao Kanhegaonkar	Male	IIT Indore	PhD
55	48137	Ms. Mansi Yadav	Female	IIT Indore
56	49666	Ms. Era Sarda	Female	IIT Indore
57	49751	Mr. Hitesh Wankhede	Male	IIT Indore
58	49810	Mr. Saurabh Saini	Male	IIT Indore	PhD
59		Mr. Haresh Jadav	Male	IIT Indore

School Short Name:

agt

Last Date Application:

Tuesday, May 30, 2023

School Type:

AIS