DIMACS Discrete Probability Seminar


Colorings and hereditary properties of graphs


B\'ela Bollob\'as, IAS
Memphis and Cambridge


M-101, Math Building
Institute for Advanced Study, Princeton University.


11:15 am
Monday, September 30, 1996

A property ${\cal P}$ of graphs is {\it hereditary} if it is invariant under vertex deletions. For a hereditary property ${\cal P}$, we write ${\cal P}^n$ for the set of graphs in ${\cal P}$ with vertex set $\{1, 2, \ldots , n\}.$ Furthermore, the ${\cal P}$-{\it chromatic number} of a graph is the minimal number of classes in a vertex partition wherein each class induces a subgraph with property ${\cal P}.$

In the talk we shall discuss two main questions concerning a hereditary property ${\cal P}$ of graphs. 1. What is the growth of the function $|{\cal P}^n|$? 2. What is the ${\cal P}$-chromatic number of almost every graph of order $n$?

The results to be presented have been obtained jointly with Andrew Thomason, and continue those of Kleitman, Rothschild, Erd\H os, Frankl, R\"odl, Scheinerman, Pr\"omel, Steger, and others. One of our tools is an extension of the classical Loomis-Whitney isoperimetric inequality.

Document last modified on September 27, 1996