Infinite Stable Graphs With Large Chromatic Number

DOI10.1090/TRAN/8570MaRDI QIDQ6345716arXivFDO

Authors Yatir Halevi, Itay Kaplan, S. Shelah

Publication date 23 July 2020

Published in arXiv

Full work available at URL https://doi.org/10.1090/TRAN/8570

Mathematics Subject Classification ID

Classification theory, stability, and related concepts in model theory (03C45) Coloring of graphs and hypergraphs (05C15)

arXiv classification

math.COmath.LO

Abstract: We prove that if $G=(V,E)$ is an $omega$-stable (respectively, superstable) graph with $chi(G)>alep{h}_0$ (respectively, $2^{alep{h}_0}$) then $G$ contains all the finite subgraphs of the shift graph $ext{Sh}_n(omega)$ for some $n$. We prove a variant of this theorem for graphs interpretable in stationary stable theories. Furthermore, if $G$ is $omega$-stable with $mathrmU(G)leq2$ we prove that $nleq2$ suffices.

This page was built for publication: Infinite Stable Graphs With Large Chromatic Number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6345716)