5707spring2020

HW 1 is due 2/5.

HW 2 is due 2/17.

HW 3 is due 2/26.

HW 4 is due 3/18.

HW 5 is due 4/8.

HW 6 is due 4/15.

HW 7 is due 5/4.

HW 8 is not due.

Time and location: M,W 11:15 AM - 01:10 PM, Lind Hall 229.

Office hours: MW 2-4pm.

The course will cover a variety of topics in graph theory and non-enumerative combinatorics. The topics include: spanning trees, graph colorings, planar graphs, Ramsey theory, probabilistic method, Hall's marriage theorem, mincut-maxflow theorem, Dilworth theorem, stable marriage problem, Arrow's theorem, NP hard problems, electrical networks, Helly's theorem, Tutte polynomial, knot invariants.

The course will be self-contained. The textbook for the course is B. Bollobas, Modern graph theory, Springer. Some of the topics covered are not in the textbook.

No exams, grading based on homeworks.

Homework: you are asked to write down the best several problems you can solve. The estimated difficulty is next to a problem, [2+] denotes an average problem, [2] a slightly easier one, [3-] a slightly harder one. Harder problems will get you more points. You are allowed (and in fact encouraged) to work in teams. However, you must write down the solutions yourself, and you must mention who were your collaborators if you had any.