Math 7014 Advanced Graph Theory, Spring 2014

Instructor: Robin Thomas
Meeting time: Tuesday, Thursday 3-4:30
Prerequisite: Math 6014 Graph Theory
About this course: The course will start where MATH 6014 left off and will cover more advanced topics in Graph Theory with the objective to introduce open problems and possible thesis topics.
Textbook: None. The basics are covered in [Diestel, Graph theory], for the rest references and handouts will be provided.
Requirements: Students registering for credit will be expected to do some (but not necessarily all) of the following:

• scribe lectures
• turn in take-home assignments
• do independent research on one of the topics suggested in class (independently or in small groups)
• present a research paper in class or in a seminar
• solve an open problem (optional)
  

Topics: The list below is tentative and may change depending on students' interests. Suggestions are welcome.

1. The Szemeredi regularity lemma and select applications. See this for the statement of the lemma. Some applications.
2. Series-parallel graphs. Notes. Slides.
3. Tree-width and similar parameters. Exercises. Slides (similar content, different format). More notes (added 2/4/14). More notes (added 2/6/14), More notes (added 3/8/14), Partition submodular functions (preliminary version), Partition submodular functions (handwritten notes from 4/1 and 4/3), Partition submodular functions (to be covered 4/8).
4. The 2 disjoint paths theorem. I will follow the Appendix in A New Proof of the Flat Wall Theorem
5. List coloring of graphs.
6. Graphs on surfaces. Representativity. Coloring graphs on surfaces.
7. Linkless and flat embeddings of graphs in 3-space.
8. Nowhere-zero flows in graphs and generalizations of the Four Color Theorem.
9. The Graph Minor Theorem.

Mini-projects:

1. A linear-time algorithm to recognize series-parallel graphs
2. Improve the simple algorithm to test whether tree-width is at most k to run in time O(n^{k+2}) or better yet in time O(n^{k+1}).
3. Give a detailed proof of the following: If G has a haven beta of order 4k, then it has a beta-free set X of size 2k such that it is possible to contract edges of a subgraph of G-beta(X) with at least one end outside X and produce a path with vertex-set X.
4. Give a detailed proof of the min-max theorem for path-width (using results we proved in class).
5. Present Bodlaender's linear-time algorithm to test whether tree-width is at most k.
6. Independent study of directed graph invariants.