Satish Pandey, Pure Mathematics, University of Waterloo
"The Dinitz Problem and Five-Colouring Plane Graphs"
G. H. Hardy firmly believed that there is no permanent place for ugly Mathematics. Following his dictum, Paul Erdos liked to talk about "The Book" in which God maintains the perfect proofs for mathematical theorems. This talk is an attempt to explore Erdos' idea of perfect proofs, and the territory we choose to explore is graph theory.
The four-colour problem was the main driving force for the development of graph theory and its first proof came in 1976 by Appel and Haken. In 1997, Robertson, Sanders, Seymour and Thomas came up with another proof using a combination of very old ideas (dating back to the 19th century) and the very new calculating powers of modern-day computers. However, the situation is still basically the same; no proof from "The Book" is in sight. So, a more modest question is whether there exists a neat proof that every plane graph can be 5-coloured. (A proof of this five-colour theorem had already been given by Heawood using Euler's formula which also serves to be the main tool for the four-colour theorem.) We give a stunning proof of 5-list colouring conjecture that is due to Carsten Thomassen. This proof is a telling example of what one can do when one finds the right induction hypothesis. It does not use Euler formula at all! In the process, we also present a simple-sounding colouring problem, raised by Jeff Dinitz in 1978.