Math6014 Graph Theory

This is a required class in the PhD program in Algorithms, Combinatorics and Optimization. The objective is to provide rigorous treatment of Graph Theory at the level of an introductory graduate course. You do not need to know much about Graph Theory, but you do need the mathematical sophistication of a beginning mathematics graduate student in order to succeed in the course. You will be required to write rigorous mathematical proofs of non-trivial results. In addition to mathematical correctness attention will be paid to writing in an elegant and aesthetically pleasing way. An assignment will be due approximately every two weeks. Thus, in addition to learning Graph Theory, you will get to practice and improve your proof-writing skills. See the links below for sample problems you will be required to solve.

Instructor: Robin Thomas

Textbook: Diestel, Graph Theory.

Other texts you may wish to consult:
Bollobas, Modern Graph Theory (recommended source)
West, Introduction to Graph Theory
Bondy and Murty, Graph Theory with Applications
Even, Graph Algorithms
Lovasz, Combinatorial Problems and Exercises
Notes on planar graphs

Lecture Schedule: Fundamentals, Matching, Connectivity, Planar graphs, Coloring, Extremal Problems, Ramsey Theory, Random Graphs.

New lecture notes in final form: Lecture 1 Lecture 2 Lecture 3 Application to algebra Lecture 4 Lecture 5 Application to baseball elimination Lecture 6 Lecture 7 Lecture 8 Lecture 9 Lecture 10 (corrected and expanded) Lecture 11 Lecture 12 Lecture 13 Lecture 14 Lecture 15 Lecture 16 Lecture 17 Lecture 18 Application to number theory Lecture 19 Lecture 20 Lecture 21 Lecture 22 Lecture 23 Lecture 24 Lecture 25 Lecture 26 Lecture 27

New lecture notes in preliminary form: Lectures 28 and 29 Lecture 29 continued

Lecture notes from last year: Lecture 1 Lecture 2 Lecture 3 Lecture 4 Lecture 5 Lecture 6 Lecture 7 Lecture 8 Lecture 9 Lecture 10 Lecture 11 Lecture 12 Lecture 13 Lecture 14 Lecture 15 Lecture 16 Lecture 17 Lecture 18 Lecture 19 Lecture 20 Lecture 21 More on lecture 21 Lecture 22 Lecture 23 Lecture 24 Lecture 25 Lecture 26 Lecture 27 Lecture 28 Lecture 29 Lecture 30
Pfaffian orientations
Application to algebra
The discharging method
A simple planarity algorithm
Eigenvalues and expanders
The Nielsen-Schreier Theorem
Extremal Graph Theory Part 1

Grades: Approximately 30% homework, 30% midterm, 40% final.

Midterm exam. You will be asked to solve problems similar to proofs done in class or problems assigned in the problem sets below. You will be permitted to bring one letter size sheet of notes, one-sided only, and you will be required to turn it in at the conclusion of the examination. Date: October 8.

Problem sets: Problem sets will be posted here. You should be able to solve these problems, because they and their variations will appear in both the midterm and the final exam.

Week 1 problems
Week 2 problems. An additional problem: Is the hypothesis |E(D)|>=2|V(D)| in the Lemma from "Application to algebra" necessary? Could it be replaced by |E(D)|>=2|V(D)|-1 or an even weaker assumption?
Week 3 problems
Week 4 problems
Week 5 problems
Week 6 problems
Week 7 problems
Due to the midterm exam and Fall recess there are no Week 8 problems
Week 9 problems
Week 10 problems
Week 11 problems
Week 12 problems (typo in problem 5 corrected)
Week 13 problems
Week 14 problems
Week 15 problems
Week 16 problems

Extra credit problems will be posted here.

Extra credit problem 1 Hint. Consider the complete bipartite graph G with vertices the rows and columns of the board. Thus the squares of the board are in 1-1 correspondence with edges of G. Consider the number of components of the subgraph of G consisting of edges painted black.
Extra credit problem 2
Extra credit problem 3
Extra credit problem 4
Extra credit problem 5
Extra credit problem 6: Let G be a 2-connected graph drawn on the sphere. On the boundary of each face there is a car that at time t=0 starts at some point of the boundary and drives in clockwise direction along the boundary and at time t=1 it ends up at the original starting place after having gone around the boundary of the face exactly once. Each car travels at its own speed, which may vary with time and may be zero at times, but no car travels backward. Prove that some two cars will collide (end up in the same point at the same time).

Final examination. December 10, 11:30-2:20 in Skiles 246. You will be permitted to bring one letter size sheet of notes, one-sided only, and you will be required to turn it in at the conclusion of the examination. You may be asked to state theorems we covered in class.

Homework: Each homework problem must be turned in on one-sided letter size paper. The text must be typed in 10pt font or larger. Figures and mathematical formulae may be drawn by hand in black ink. Do not fold pages or bend corners. Your work must be scannable at 300dpi. Electronic submission is allowed only in pdf format. Due dates will be strictly enforced. Clarity of exposition, ease of expression, mathematical elegance and overall physical appearance will all be factors in grading. A signed cover page must accompany each submission.

Homework 1 Solutions are available on T-square.
Homework 2 Solutions are available on T-square.
Homework 3 Solutions are available on T-square.
Homework 4 Solutions are available on T-square.
Homework 5 Solutions are available on T-square.
Homework 6 Due November 20.

Honor Code: Discussing class material including problem sets is encouraged. However, no collaboration is allowed on problems assigned  for homework, midterm or final.

Office hours: Tuesday 1:45-2:15, Thursday 12:00-12:30 and by appointment.

Office: 217B Skiles.

This document: http://www.math.gatech.edu/~thomas/TEACH/6014