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.


dimacs-www@dimacs.rutgers.edu
Document last modified on September 27, 1996