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