Thu, 20 May 2021
11:30
11:30
Virtual
Chromatic numbers of Stable Graphs
Yatir Halevi
(Ben Gurion University of the Negev)
Abstract
This is joint work with Itay Kaplan and Saharon Shelah.
Given a graph $(G,E)$, its chromatic number is the smallest cardinal $\kappa$ of a legal coloring of the vertices. We will mainly concentrate on the following strong form of Taylor's conjecture:
If $G$ is an infinite graph with chromatic number$\geq \aleph_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).
If $G$ is an infinite graph with chromatic number$\geq \aleph_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 sketch a proof for a variant of this conjecture for $\omega$-stable\superstable\stable graphs. The proof uses a generalization of Ehrenfeucht-Mostowski models, which we will (hopefully) introduce.