Graph Theory
642:581
Instructor: Shubhangi Saraf
Email: shubhangi.saraf@rutgers.edu
Timing: Mon, Wed 5 pm – 6:20 pm
Location: HILL 425
Office hours: Wed 2 pm – 3 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
HOMEWORK-1
(due Feb 20)
HOMEWORK-2
(due March 13)
HOMEWORK-3
(due April 8)
HOMEWORK-4
(due May 6)
Schedule:
§ Lecture 1 (Wed 01/23): Administrative details, course overview, preliminaries
§ Lecture 2 (Mon 01/28): Trees, cycles, paths
§ Lecture 3 (Wed 01/30): Flows and matchings 1 (Max-flow min-cut and variations)
§ Lecture 4 (Mon 02/04): Flows and matchings 2 (Menger’s thm, Hall’s thm, Stable matchings)
§ Lecture 5 (Wed 02/06): Planar graphs
§ Lecture 6 (Mon 02/11): Planar graphs 2
§ Lecture 5 (Wed 02/13): Graph coloring
§ Lecture 6 (Mon 02/18): Graph coloring, Extremal Graph Theory (Forbidden subgraphs – cycles, paths, Hamiltonian cycles)
§ Lecture 7 (Wed 02/20): Extremal Graph Theory (Forbidden subgraphs 2– Turan’s Theorem, Zarankiewicz’s Theorem)
§ Lecture (Mon 02/25): Cancelled (Makeup class from 6:30 to 8 pm on March 4)
§ Lecture (Wed 02/27): Cancelled (Makeup class from 6:30 to 8 pm on March 6)
§ Lecture 8,9 (Mon 03/04): Erdos-Stone Theorem, Ramsey Theory 1
§ Lecture 10,11 (Wed 03/06): Ramsey Theory 2
§ Lecture 12 (Mon 03/11): Probabilistic Method 1
§ Lecture 13 (Wed 03/13): Probabilistic Method 2
§ No Class on Mon 03/18 and Wed 03/20 (Spring Break)
§ Lecture 14 (Mon 03/25): Second moment method
§ Lecture 15 (Wed 03/27): Random Graphs 1 (threshold phenomena, balanced graphs)
§ Lecture 16 (Mon 04/01): Random Graphs 2 (connectivity)
§ Lecture 17 (Wed 04/03): Random Graphs 3 (clique number)
§ Lecture 18 (Mon 04/08): 0-1 law for random graphs
§ Lecture 19 (Wed 04/10): Adjacency matrix and Eigenvalues
§ Lecture 20 (Mon 04/15): Spectral properties of graphs
§ Lecture 21 (Wed 04/17): Quasirandom graphs
§ Lecture 22 (Mon 04/22): Quasirandom graphs, Szemeredi’s regularity lemma
§
Related Courses: