Combinatorics Seminar

When: Sunday, May 10, 10am
Where: Schreiber 309
Speaker: Omri Ben Eliezer, Tel Aviv U.
Title: Local and Global Colorability of Graphs

Abstract:

A well known result of Erdos states that there exist graphs with arbitrarily large girth and chromatic number. In particular, there exist graphs with arbitrarily large chromatic number, in which every subgraph of small radius is 2-colorable.

We show that for any fixed $c \geq 3$ 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 $n^\frac{1}{r+1}$ up to a multiplicative factor 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