Math 443 Section 101
GRAPH THEORY
Online Course Material

NEWS

Our midterm is scheduled for Wednesday Feb 28, after the break.

Our Final exam is scheduled for Saturday, April 21 at 8:30 am in BUCH B215 . Early. It is a 3 hour exam.
• Notations. I will print up and give you a copy for final exam.
• Topics covered in the course. at least an outline of the major ideas. I seem to be missing a card trick. The exam wonÕt have detailed Ramsey Theory, Extremal Graph Theory.
• Course Outline: grading scheme etc.

• This is an Honours course that has substantial use of proofs. The subject of Graph Theory can often be conveyed through pictures and students (and myself) find this makes the subject more appealing.
I will devote about 1/3 of the class time to student presentations of solutions to problems. My intention is to give you a sheet for the problems we are looking at and ask you to indicate whether you are ready to present, somewhat ready or not ready. Then I will select some presenters from those who say they are ready. Some portion of your grade comes from the sheet and some from the presentation. The presentation in the best case will be complete and clear and well delivered. Grading will be caring. I will endeavour that everyone presents at least 2 problems by the end of the course.

• Problems 1-4: for presentation Friday Jan 12.
• Problems 5-9: for presentation Monday Jan 22 (also problem 4 from previous set).
• Assignment 1 Due Friday Jan 26 Solutions
• Problems 10-16: for presentation Friday Feb 2 (also problem 9 from previous set).
• Assignment 2 Due Wednesday Feb 14 Solutions
• Problems 17-22: for some initial presentations Friday Feb 16 but also the subsequent week Friday March 2 after the break.
• Practice Midterm From 2013. As always, I do not post solutions. I will endeavour to have an office hour on Tuesday Feb 27 but also should be available before class 2-3 on Monday and 2-3 on Wednesday.
• Midterm Solutions
• Problems 23-27: Presentations on Friday March 9 will include problem 22 plus perhaps problems 23,24,25.
• Assignment 3 Due Friday March 9 but I will accept it on Monday March 12. Solutions
• Problems 28-33: Presentations on Friday March 16 will include problem 28,29 with remaining problems 30,31,32,33 for Friday March 23.
• Assignment 4 Due Friday March 16 but I will accept it on Monday March 19. Solutions
• Assignment 5 Our last assignment will be due Wednesday March 28. Solutions
• Problems 34-38: Presentations on Wednesday April 4 and perhaps April 6. Cookies on April 6
• 2013 Final exam. As always, I do not post solutions.

• Various texts would be useful. The book by Reinhard Diestel is an excellent overview at a slightly higher level than some. The UBC library gives you access to this Springer text in electronic form. Also Diestel website
The text by Doug West is readily accessible. Any notes I type may look authoritative when typed so be wary. They may look perfect but may still contain errors! I don't have an editor.
I arrive most days by 9:00 or so. I will be teaching MATH 340 from 12-1 MWF. I typically do not read my email from home (i.e. evenings and weekends).

There is lots of information on Wikipedia about some of the big advances in Graph Theory. I should have pointers to them. The Robertson-Seymour Graph Minors project is a huge enterprise that eventually brought in Robin Thomas and Maria Chudnovsky. Robertson Seymour Theorem

The perfect graph conjecture was made by Claude Berge in 1963 and was finally proved in 2006 by Chudnovsky, Robertson, Seymour and Thomas. Strong Perfect Graph Theorem

We proved in class that if the minimum degree of G is at least n/2, then G has a Hamilton cycle. Christofides, Kuhn and Osthus (2012) proved that if the minimum degree is (1/2+epsilon)n, then one can find n/8 edge disjoint Hamilton cycles where n/8 is essentially best possible.

Graphs appear in many applications. Often unexpectedly. Some notes on the problem of squared rectangles. The interesting outcome of this is searching for squared rectangles of n squares con be done by generating all (planar) graphs with n edges.
• A squared rectangle, A squared rectangle with horizontal line network, A squared rectangle with vertical line network, A squared rectangle with both line networks,
• A squared rectangle, A squared rectangle with horizontal line network, A squared rectangle with both line networks,

• De Bruijn Card Trick   Great for students of a variety of ages. But can you do bit calculations in your head?