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
