***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Date: Thursday 9th October, 3:00 in Fine Hall 224.
 
Speaker: Omri Ben Eliezer (Tel Aviv and IAS)

Title: Local and global colorability of graphs


It is shown that for any fixed c > 2 and r, the maximum possible 
chromatic number of a graph on n vertices in which every subgraph
of radius at most r is c-colorable is equal to n^{1/(r+1)} up to 
a factor poly-logarithmic in n. The proof is based on a careful 
analysis of the local and global colorability of random graphs 
and implies, in particular, that a random n-vertex graph with the 
right edge probability has typically a chromatic number as above 
and yet most balls of radius r in it are 2-degenerate.

Joint work with Noga Alon.


                       -----------

Next week: Jie Ma

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)