Colourings and Hereditary Properties of Graphs
A property P of graphs is hereditary if it is invariant under vertex deletions. A hereditary property that is invariant under edge deletions is said to be monotone. Much of classical graph theory is concerned with the maximal number of edges of a graph with n vertices having a specified monotone property. For well over a decade, much attention has been paid to general hereditary properties: their asymptotic enumeration, their global structure, the `largest' graphs with the property, and colouring random graphs with the property. Somewhat surprisingly, the asymptotic density of general hereditary properties exhibits a certain phase transition, and the P-chromatic number of a random graph Gn,p is highly concentrated for every fixed p and every hereditary property P
In the talk we shall review a number of beautiful results of Kleitman, Rothschild, Erdös, Frankl, Rödl, Scheinerman, Prömel, Steger, and others, and we shall present the latest developments, most of which were obtained jointly with Andrew Thomason. One of our tools is an extension of the classical Loomis-Whitney isoperimetric inequality.