Coloring Superstable Graphs

Seminar
Speaker
Yatir Halevi (BGU)
Date
12/10/2020 - 13:00 - 11:00Add to Calendar 2020-10-12 11:00:00 2020-10-12 13:00:00 Coloring Superstable Graphs 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 following 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 a proof for \omega-stable graphs and a proof of a generalization for superstable graphs. If time permits will discuss stable graphs in general. No previous knowledge in model theory or graph theory is needed. Joint work with Itay Kaplan and Saharon Shelah. zoom אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
zoom
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 following 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 a proof for \omega-stable graphs and a proof of a generalization for superstable graphs. If time permits will discuss stable graphs in general.
No previous knowledge in model theory or graph theory is needed.

Joint work with Itay Kaplan and Saharon Shelah.

Last Updated Date : 04/10/2020