Around Taylor’s Conjecture and Model-Theoretic Tameness

Abstract: Given a graph (G, E), its chromatic number is the smallest cardinal $\kappa$ admitting a legal coloring of the vertices. The strong Taylor's conjecture states the following:

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 and Komjáth; however, a variant of it still holds for $\omega$-stable, superstable, or stable graphs. One can also restrict the conjecture and ask when G contains all finite subgraphs of the complete graph. We give answers to this question when the edge relation of the graph is stable or when the graph itself is simple.

Joint work with Itay Kaplan and Saharon Shelah

combinatoricslogic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic