# DIMACS Discrete Probability Seminar

## Title:

Colorings and hereditary properties of graphs

## Speaker:

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

## Place:

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

## Time:

- 11:15 am
- Monday, September 30, 1996

Abstract:
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