Math 1230: Graph Theory


Professor Richard Kenyon
Tel. 863-6406
rkenyon -at- math dot brown dot edu
office: Kassar 305
Office hours: Mondays 12:30-1:30pm

Text: Introduction to Graph Theory, 2nd edition by Douglas West

Course outline: We will cover most of the material in chapters 1-7, and possibly some material of chapter 8.

There will be homeworks collected weekly and one midterm.
The final grade will be weighted as follows: Homework 35%, midterm 20%, final 45%.

TA sessions: Mondays 6-7pm, BH160. TA: Laura Shea

Final Project:

Instead of a final exam we will have a final project. I expect around 10 typed pages on a subject of your choice related to graph theory. The write-up should contain some result and its proof. You will also give a 15 minute presentation of your project in class.

Possible project ideas:

Graph genus
Tutte polynomial
4-coloring problem
NP-completeness
Random planar maps
Erdos-Renyi random graphs
Graphons
Szemeredi regularity Lemma
Expander graphs

Homework:

Late homework will not be accepted. The lowest homework grade will be dropped.
It is expected that your homework should involve up to 10 hours of work per week. If you are spending considerably more time than this, let me know.

Homework 1 due Tuesday Jan 31 in class
1.1.11, 1.1.14, 1.1.21, 1.1.22, 1.1.27

Homework 2 due Tuesday Feb. 7 in class
1.1.26, 1.1.29, 1.1.36, 1.1.42, 1.1.43

Homework 3 due Tuesday Feb. 14 in class
1.2.17, 1.2.18, 1.2.29, 1.2.39, 1.3.2, 1.3.9, 1.3.14

Homework 4 due Thursday Feb. 23 in class
1.3.59, 1.4.14, 1.4.15, 1.4.38, 2.1.20, 2.1.23

Homework 5 due Tuesday Mar 7 in class
2.2.6, 2.2.10, 2.2.12, 2.3.3, 2.3.10, 2.3.16, 2.3.23

Homework 6 due Tuesday Apr 4 in class
3.1.18, 3.1.24, 3.3.6, 4.1.8, 4.1.31, 4.2.8, 4.2.35