**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 :**

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:**