550.672 Graph Theory

550.472/672
GRAPH THEORY
SPRING 2008

Instructor:
Dr. Donniell Fishkind, 304-B Whitehead Hall, <fishkind@ams.jhu.edu>

Office_Hours:
MWF 11am-noon, and by appointment.

Lectures:
MWF 9am-9:50am, Whitehead 304.

Textbook:
Introduction to Graph Theory by Douglas West, 2nd edition (Prentice Hall).

Teaching_Assistant:

Section for 550.472 is Thursday 3:00pm-3:50pm in NEB12. TA is Andrey Rukhin <rukhin@ams.jhu.edu>, office hours Monday 3:30-4:30pm, Wednesday 3:30pm-4:30pm.
Section for 550.672 is Friday 10:00am-10:50am in Whitehead 304. TA is Andrey Rukhin <rukhin@ams.jhu.edu>, office hours Monday 3:30-4:30pm, Wednesday 3:30pm-4:30pm.

Description:
(From JHU Manual) This course focuses on the mathematical theory of graphs; a few applications and algorithms will be discussed. Topics include trees, connectivity, Eulerian and Hamiltonian graphs, matchings, edge and vertex colorings, independent sets and cliques, planar graphs and directed graphs. An advanced topic completes the course. Familiarity with linear algebra and basic counting methods such as binomial coefficients is assumed. Comfort with reading and writing mathematical proofs is required.

Syllabus:

Bipartite graphs, trees, minimum spanning trees

Independent sets, cliques, matchings, vertex and edge covers, vertex and edge colorings

Gallai's Theorem, Berge's Theorem, Hall's Theorem, Konig-Egervary Theorem, Vizing's Theorem, Konig's Theorem

Ramsey Numbers and probabilistic bounds

Planar graphs, planar duality, Euler characteristic, bounds on edges

Four Color Theorem, Kuratowski's Theorem, Wagner's Theorem

Surfaces of higher genus

Eulerian tours, Hamiltonian cycles, Traveling Salesman Problem, approximation algorithms

Shortest Path Problem, Max Flow Min Cut Problem

Linear and integer programming formulations and duality

Network reliability

Other topics as time permits

Grades:
Weekly homework and exams. The exams may be in-class or take-home. It is likely that there will be at least one of each. For the take-home exams you will not be permitted to consult with any person or text, including the official class text, nor any web materials or (at any time) exams and/or solutions from previous years. You may, however, consult lecture notes that you write this semester. It is therefore very important that you maintain a good set of lecture notes. Take-home exams are only possible when I can trust the integrity of the exam. Any violation of academic ethics will be prosecuted vigorously, in accordance with the procedures outlined in the student manual.

General:
Everyone is responsible for attending all lectures and hearing all announcements.

Extra_help:
You are welcome to visit me anytime. Additional help is available through the teaching assistants. On the second floor of Whitehead Hall there is a large room with a glass wall off the main hallway. This is the room in which the TAs hold their office hours. By departmental policy, ALL TAs HOLDING OFFICE HOURS--even if not assigned to our course, as long as they are departmental graduate students--are obligated to assist you to the best of their ability. A list of TAs and their office hours is posted around the office of Dept of Applied Mathematics and Statistics, and is updated when changes are made.

Homework:

Assignment 1, due Wednesday, Feb 13. Problems 1.1.30, 1.1.31, 1.1.41, 1.2.20, 1.2.26, 8.6.4. Undergraduates may skip the problem of their choice, or may do all for extra credit (but must indicate which one they are doing for extra credit).
Assignment 2, due Thurday, Feb 21. Problems 1.3.1, 1.3.32, 2.1.18, 2.1.23, 2.1.29, 2.1.30. Undergraduates may skip the problem of their choice, or may do all for extra credit (but must indicate which one they are doing for extra credit).
Assignment 3, due Thursday, Feb 28. FOR 550.472 students: Problems 3.1.8, 3.1.19, 3.1.20, 3.1.29, 3.1.40, and you may do 3.1.24 for extra credit. FOR 550.672 students: Problems 3.1.13, 3.1.24, 3.1.25, 3.1.29, 3.1.39, 3.1.40. Both 550.472 and 550.672 should think about 3.1.18 but needn't hand it in.
Assignment 4, due Thursday, March 6: Problems 5.1.20, 5.1.25, 5.1.38, 5.1.39. The students taking 550.672 should also do 3.1.42.
Assignment 5, due Thursday, April 3. Problems 6.1.14, 6.1.25, 6.1.29, 6.3.5, 6.3.6 (to make it easier, you can change "at most 12 vertices" to "less than 12 vertices" and "at most 32 edges" to "less than 30 edges"). Students taking 550.472 should do 6.3.3, and students taking 550.672 should do 6.1.36.
Special Assignment, due Thursday, April 10. Download from here after your lecture notes are completely in order... since you can only use lecture notes in your handwriting that you wrote this semester. Read the instructions carefully. 550.472 can skip the problem of their choice.
Assignment 7, due Thursday, May 1. Problems 4.3.2, 4.3.6, 4.3.7, 4.3.8, 4.3.13a, 4.3.14. Students in 550.472 can skip the problem of their choice.
Solutions to hw will be available at Andrey Rukhin's website.
Solutions to Exam 1 are here.

Last modified 16 January, 2008 by Donniell Fishkind.

Return to Applied Mathematics and Statistics home page.

Instructor:	Dr. Donniell Fishkind, 304-B Whitehead Hall, `<fishkind@ams.jhu.edu>`
Office_Hours:	MWF 11am-noon, and by appointment.
Lectures:	MWF 9am-9:50am, Whitehead 304.
Textbook:	Introduction to Graph Theory by Douglas West, 2nd edition (Prentice Hall).
Teaching_Assistant:	Section for 550.472 is Thursday 3:00pm-3:50pm in NEB12. TA is Andrey Rukhin `<rukhin@ams.jhu.edu>`, office hours Monday 3:30-4:30pm, Wednesday 3:30pm-4:30pm. Section for 550.672 is Friday 10:00am-10:50am in Whitehead 304. TA is Andrey Rukhin `<rukhin@ams.jhu.edu>`, office hours Monday 3:30-4:30pm, Wednesday 3:30pm-4:30pm.
Description:	(From JHU Manual) This course focuses on the mathematical theory of graphs; a few applications and algorithms will be discussed. Topics include trees, connectivity, Eulerian and Hamiltonian graphs, matchings, edge and vertex colorings, independent sets and cliques, planar graphs and directed graphs. An advanced topic completes the course. Familiarity with linear algebra and basic counting methods such as binomial coefficients is assumed. Comfort with reading and writing mathematical proofs is required.
Syllabus:	Bipartite graphs, trees, minimum spanning trees Independent sets, cliques, matchings, vertex and edge covers, vertex and edge colorings Gallai's Theorem, Berge's Theorem, Hall's Theorem, Konig-Egervary Theorem, Vizing's Theorem, Konig's Theorem Ramsey Numbers and probabilistic bounds Planar graphs, planar duality, Euler characteristic, bounds on edges Four Color Theorem, Kuratowski's Theorem, Wagner's Theorem Surfaces of higher genus Eulerian tours, Hamiltonian cycles, Traveling Salesman Problem, approximation algorithms Shortest Path Problem, Max Flow Min Cut Problem Linear and integer programming formulations and duality Network reliability Other topics as time permits
Grades:	Weekly homework and exams. The exams may be in-class or take-home. It is likely that there will be at least one of each. For the take-home exams you will not be permitted to consult with any person or text, including the official class text, nor any web materials or (at any time) exams and/or solutions from previous years. You may, however, consult lecture notes that you write this semester. It is therefore very important that you maintain a good set of lecture notes. Take-home exams are only possible when I can trust the integrity of the exam. Any violation of academic ethics will be prosecuted vigorously, in accordance with the procedures outlined in the student manual.
General:	Everyone is responsible for attending all lectures and hearing all announcements.
Extra_help:	You are welcome to visit me anytime. Additional help is available through the teaching assistants. On the second floor of Whitehead Hall there is a large room with a glass wall off the main hallway. This is the room in which the TAs hold their office hours. By departmental policy, ALL TAs HOLDING OFFICE HOURS--even if not assigned to our course, as long as they are departmental graduate students--are obligated to assist you to the best of their ability. A list of TAs and their office hours is posted around the office of Dept of Applied Mathematics and Statistics, and is updated when changes are made.