Graph Theory
642:581
Instructor: Shubhangi Saraf
Email: shubhangi.saraf@rutgers.edu
Timing: Mon, Thurs:
12 – 1:20 pm
Location: HILL 425
Office hours: Wed 1:30 pm – 2:30 pm (Hill 426)
Prerequisites:
Basic combinatorics, basic linear algebra, mathematical maturity
Description: This course will serve as a graduate
course in graph theory. For a large part of the course we will follow the text
by Bela Bollobas on Modern Graph Theory. Some of the
topics we will cover include: Matchings, cuts, flows, connectivity, planar
graphs, graph colorings, random graphs, extremal graph theory, Ramsey theory,
linear algebra methods, and expander graphs
Problem sets will be posted every 2-3 weeks.
Recommended Text: Modern graph theory
by Bela Bollobas
Also available online:
Graph Theory by Reinhard Diestel
Schedule:
§ Lecture 1 (Thursday 01/23): Administrative details, course overview, preliminaries
§ Lecture 2 (Monday 01/27): trees, cycles, paths
§ Lecture 3 (Thursday 01/30): Planar graphs
§ Lecture 4 (Monday 02/03): Flows and matchings 1 (Max-flow min-cut and variations)
§ Lecture 5 (Thursday 02/06): Flows and matchings 2 (Max-flow min-cut and variations)
§ Lecture 6 (Monday 02/10): Menger’s theorem, graph coloring
§ Lecture 7 (Thursday 02/13): Graph coloring - Brook’s theorem
§ Lecture 8 (Monday 02/17): Graph coloring- Vizing’s theorem
§ Lecture 9 (Thursday 02/20): Graph coloring: Planar graphs, list coloring
§
Lecture
10 (Monday 02/24): Extremal Graph Theory
(Forbidden subgraphs – paths, Hamiltonian cycles)
§ Lecture 11 (Thursday 02/27): Extremal Graph Theory (Forbidden subgraphs 2– Turan’s Theorem, Zarankiewicz’s Theorem)
§
Lecture 12
(Monday 03/02): Erdos-Stone Theorem, Ramsey
Theory 1
§
Lecture 13
(Thursday 03/05): Ramsey Theory 2
§
Lecture 14
(Monday 03/09): Ramsey Theory 3
§
Lecture 15
(Thursday 03/12): Class cancelled due to Covid-19
§ No Class on Mon 03/16 and Thu 03/19 (Spring Break)
§
Lecture 16
(Monday 03/23): Probabilistic Method 1
§ Lecture 17 (Thursday 03/26): Probabilistic Method 2
§
Lecture 18
(Monday 03/30): Second moment method
§ Lecture 19 (Thursday 04/02): Random Graphs 1 (threshold phenomena, balanced graphs)
§
Lecture 20
(Monday 04/06): Random Graphs 2 (connectivity)
§
Lecture 21
(Thursday 04/9): Random Graphs 3 (clique number)
§
Lecture 22
(Monday 04/13): Adjacency matrix and Eigenvalues
§
Lecture 23
(Thursday 04/16): Spectral properties of graphs
§ Lecture 24 (Monday 04/20): Quasirandom graphs
§
Lecture 25
(Thursday 04/23): Szemeredi’s regularity lemma
§
Lecture 26
(Monday 04/27): Applications of Szemeredi’s
regularity lemma
Related Courses: