check
Logic Seminar - Yatir Halevi | Einstein Institute of Mathematics

Logic Seminar - Yatir Halevi

Date: 
Wed, 29/01/202009:45-11:45
Location: 
Ross building - Room 63
Yatir Halevi will speal about Coloring Stable Graphs.


Title: Coloring Stable Graphs

Abstract: Given a graph G=(V,E), a coloring of G in \kappa colors is a
map c:V\to \kappa in which adjacent vertices are colored in different
colors. The chromatic number of G is the smallest such \kappa.
We will briefly review some questions and conjectures on the chromatic
number of infinite graphs and will mainly concentrate on the strong
form of Taylor's conjecture:
If G is an infinite graph with chromatic number\geq \alepha_1 then it
contains all finite subgraphs of Sh_n(\omega) for some n, where
Sh_n(\omega) is the n-shift graph (which we will introduce).
The conjecture was disproved by Hajnal-Komjath.
However, we will present an elementary proof for \omega-stable graphs
and if time permits will discuss stable graphs in general.
Joint work with Itay Kaplan, Saharon Shelah (and parts with Elad Levi)